Click here to Skip to main content
14,420,831 members
Rate this:
Please Sign up or sign in to vote.
See more:
Guys I wanna perform this loop hopefully in O(n). I just need to calculate the minimum of distance between the second and the first occurrence of all elements in an array.

for example abcdeabb the answer for m = 1

What I have tried:

m = INT_MAX
for(int i = 0; i<s.length(); ++i)
{
    for(int j = i+1; j<s.length(); ++j)
    {
        if(s[i] == s[j] and m > j - i)
        {
            m = j - i;
            if(m == 1)
                break;
        }
    }
}
Posted
Updated 17-Dec-19 23:16pm
v2
Rate this:
Please Sign up or sign in to vote.

Solution 1

Quote:
How do optimise this loop for O(n) or O(nlogn)

Rule of seasoned programmers: first, make it right, then make it fast.
Quote:
for example abcdeabb the answer for m = 1

There is no way the answer is 1 !
The example have 2 matches
First match is abcdeabb
               ^    ^
and second match is abcdeabb
                     ^    ^

To get answer = 1
the match is abcdeabb
                   ^^

and this is second and third occurrence of b.
Your algorithm is correct if a letter appear no more than 2 times is string.

Instead of checking a letter with remainder of string, my first approach would be to check a letter with beginning of string to ensure that a letter is checked with first occurrence.

I don't think your goal performance is possible.
   
Comments
Stefan_Lang 18-Dec-19 4:18am
   
Agreed on all accounts but the last: you can do it in O(N) (actually O(N+C), see solution 2)
Rate this:
Please Sign up or sign in to vote.

Solution 2

You can make it O(N+C) where C is the number of valid characters in your alphabet. Try this:

#include <iostream>
#include <limits>

int min_repetitions(char const* text) {

    int min_rep = -1; // indicates that no repetitions were found

    if (!text)
        return -1;

    std::ptrdiff_t positions[256] = {0 }; // o(number of valid characters)

    min_rep = std::numeric_limits<int>::max();
    bool repetition_found = false;
    
    for (char const* ptext = text; *ptext != 0; ++ptext) {
        char c = *ptext;
        if (positions[c]==0) {
            positions[c]=ptext-text;
        }
        else if (positions[c]>0) {
            int distance = ptext-text - positions[c];
            if (distance < min_rep) {
                min_rep = distance;
                repetition_found = true;
            }
            positions[c] = -1; // disable future checks
        }
    }
    
    if (!repetition_found)
        min_rep = -1;

    return min_rep;
}
int main()
{
    char test[] = "abcdeabb";
 
    int min_rep = min_repetitions(test);
    if (min_rep >= 0)
        std::cout << "Minimum repetition distance for " << test << " is: " << min_rep << std::endl;
    else
        std::cout << "The text "<< test << " has no repetitions" << std:.endl;

    return 0;
}
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month



CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100