14,420,831 members
Rate this:
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:

## 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
^    ^```

```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.
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:

## 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;
}```