O(nlogn) Lexicographically minimal rotation code but tle on this particular case

Question

Based on a small suggestion here , this code tries to find lexicographically minimal rotation (question) by successively comparing two adjacent substrings in the very left , that can potentially give us the answer.

Note : Will refer lexicographically smaller char as smaller char and 0-indexing is used

Ex - "abbaad"
Final answer - "aadabb"

My approach is :-

1. Find out the indices of all the smallest characters. In the above example, [0,3,4]

2. Start from two leftmost indices :

   First smallest index -> pointed by "left" pointer. Here , 0

   Second smallest index -> pointed by "right" pointer. Here , 3

3. Compare corresponding next characters until you find a mismatch. Which is done inside this loop :-

     while(i<n/2){
       // code 
     }

The mismatch in our example is when 'b' at 1 is compared to 'a' at 4.

4. Update the 'left' and 'right' pointers accordingly. Here,

   ->left is set to right

   ->right becomes right + 1

This naive algo will give O(n^2) complexity on the test cases like "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .

The observation is that while we are in the process of comparing corresponding next characters from 'left' and 'right' pointers , if we touch the 'right' pointer (from behind) , then we can remove all the indices of the smallest chars (that we computed in the first step) that lies within the substring of the 'right' pointer that we have traversed so far.

I'll write here but you can also see the first hyperlink.

Ex - "aaaaaaa" : let's say in mid-way , 'left' is 0 and 'right' is 3 . Then for i = 3 , left + i = 3 which is equal to right .

In the first step , our array that stored smallest char indices would be [0,1,2,3,4,5,6] . Then we would remove [3,4,5] from it.

The 'left' pointer stays at 0. But 'right' is now at 6. Hence, we skipped unnecessary computations that would arise with 'right' having values 4 and 5.

But , my solution is giving me tle on the case where string is char 'a' repeated 10^6 times.

I have tried rechecking a lot and also all possible ways of small optimisations like cin.tie(NULL) and using reserve on vector that stored smallest char indices.

#include <bits/stdc++.h>
using namespace std;
#define std_modulo 1000000007
void minimal_rotation()
{
    string s;
    cin >> s;
    if (s.size() == 1)
    {
        cout << s;
        return;
    }
    // Just some code to extract smallest indices
    vector<int> v;
    v.reserve(1000000);
    for (int i = 0; i < s.size(); i++)
    {
        if (v.empty())
        {
            v.push_back(i);
        }
        else
        {
            if (s[i] - 'a' <= s[v.back()] - 'a')
            {
                v.push_back(i);
            }
        }
    }

    vector<int> small_indices; // vector of smallest char indices
    small_indices.reserve(1000000);
    small_indices.push_back(v.back());

    for (int i = v.size() - 2; i >= 0; i--)
    {
        if (s[v[i]] == s[v[i + 1]])
        {
            small_indices.push_back(v[i]);
        }
        else
        {
            break;
        }
    }
    reverse(small_indices.begin(), small_indices.end());

    // vector of smallest indices ready
    // actual algo begins now
    s = s + s;
    int n = s.size();
    if (small_indices.size() == 1)
    {
        for (int i = *small_indices.begin(); i < n / 2; i++)
        {
            cout << s[i];
        }
        for (int i = 0; i < *small_indices.begin(); i++)
        {
            cout << s[i];
        }
        return;
    }

    // if more than 1 smallest indices
    int left = 0;
    int right = 1;
    while (right < small_indices.size())
    {
        int i = 0;
        while (i < n / 2)
        {
            // If we touched 'right' pointer from behind
            if (small_indices[left] + i == small_indices[right])
            {
                int removing_range = small_indices[right] + i;
                while (right < small_indices.size() && small_indices[right] < removing_range)
                {
                    right++;
                }
                break;
            }
            else
            {
                if (s[small_indices[left] + i] < s[small_indices[right] + i])
                {
                    right++;
                    break;
                }
                else if (s[small_indices[left] + i] > s[small_indices[right] + i])
                {
                    left = right;
                    right = left + 1;
                    break;
                }
                else
                {
                    i++;
                }
            }
        }
    }
    cout << s.substr(small_indices[left], n / 2);
}
int main()
{
    minimal_rotation();
}

Answer 1

You've already found the performance issue yourself (which is great), so I'll just comment on the code in general.

Unlearn bad leetcode practices

It seems like this was a programming challenge from a site like LeetCode, and you've picked up some bad coding habits from there.

Don't use #include <bits/stdc++.h>: it is not a standard C++ header file. Instead, #include the official header files that are appropriate for the functions you are using.

Avoid using namespace std: you are pulling in all of std, including things you don't know. Either don't use it and just write std:: where necessary, or be more specific, like writing using std::vector.

Make minimal_rotation() a function that takes and returns a string

It's a bit weird that main() only calls minimal_rotation(), and that the latter both handles I/O and the actual minimal rotation algorithm. A better way to organize the code would be to do the I/O in main(), and pass a string to minimal_rotation(), which then returns the rotated string, which can then be printed from main().

Use better size estimates for reserve()

You unconditionally reserve(1000000), however if the input is smaller than that, you allocated too much memory, and if the input is much larger, then you still suffer from repeated reallocations. Use the size of the input to reserve memory for the temporary arrays.

Avoid unnecessary work

You can combine the first two for-loops and avoid some work. In the first loop, whenever s[i] < s[v.back()], you can just do v.clear() before pushing back i. You'll end up with the indices of only the smallest character that's already in the correct order. Note that clear() doesn't free any memory, so it's a very cheap operation.

Answer 2

After much scrutinization , I have found another optimization. And the solution got accepted . I don't know about Code Review's policy but it would be really helpful for all if this question stays here.

The optimisation :-

For the case , where the character mismatches and the right-er charachter is bigger , then in the above code we were just incrementing the 'right' pointer .

The answer is that we shouldn't just increment the 'right' pointer but do as we did with the case of 'right' pointer touched from behind . That is, remove all the smallest char indices that lies within the range of 'right' part that we traversed so far , it is not difficult to guess why. Because at the same distance from 'left' and 'right' pointer, 'left' has a smaller char than 'right' so 'right' part can never be minimal rotation.

The test case that actually caused the problem has a 'b' somewhere deep inside the ocean of 99999 no of 'a' and that caused the actual problem.

Accepted code :- (i have comented the place where the changes took place)

#include <bits/stdc++.h>
using namespace std;
#define std_modulo 1000000007
void minimal_rotation()
{
    
    string s;
    cin >> s;
    if (s.size() == 1)
    {
        cout << s;
        return;
    }
    
    // Just some code to extract smallest indices
    vector<int> v;
    v.reserve(1000000);
    for (int i = 0; i < s.size(); i++)
    {
        if (v.empty())
        {
            v.push_back(i);
        }
        else
        {
            if (s[i] - 'a' <= s[v.back()] - 'a')
            {
                v.push_back(i);
            }
        }
    }

    vector<int> small_indices; // vector of smallest char indices
    small_indices.reserve(1000000);
    small_indices.push_back(v.back());

    for (int i = v.size() - 2; i >= 0; i--)
    {
        if (s[v[i]] == s[v[i + 1]])
        {
            small_indices.push_back(v[i]);
        }
        else
        {
            break;
        }
    }
    reverse(small_indices.begin(), small_indices.end());

    // vector of smallest indices ready
    // actual algo begins now
    s = s + s;
    int n = s.size();
    if (small_indices.size() == 1)
    {
        for (int i = *small_indices.begin(); i < n / 2; i++)
        {
            cout << s[i];
        }
        for (int i = 0; i < *small_indices.begin(); i++)
        {
            cout << s[i];
        }
        return;
    }

    // if more than 1 smallest indices
    int left = 0;
    int right = 1;
    while (right < small_indices.size())
    {
        int i = 0;
        while (i < n / 2)
        {
            // If we touched 'right' pointer from behind
            if (small_indices[left] + i == small_indices[right])
            {
                int removing_range = small_indices[right] + i;
                while (right < small_indices.size() && small_indices[right] < removing_range)
                {
                    right++;
                }
                break;
            }
            else
            {
                if (s[small_indices[left] + i] < s[small_indices[right] + i])
                {
                    // edited part goes here.
                    int removing_range = small_indices[right] + i;
                    while (right < small_indices.size() && small_indices[right] < removing_range)
                    {
                        right++;
                    }
                    break;
                    // edited part ends here 


                    // earlier we had only "right++" 
                }
                else if (s[small_indices[left] + i] > s[small_indices[right] + i])
                {
                    left = right;
                    right = left + 1;
                    break;
                }
                else
                {
                    i++;
                }
            }
        }
    }
    cout << s.substr(small_indices[left], n / 2);
}
int main()
{
    minimal_rotation();
}