0
\$\begingroup\$

I am trying to solve https://www.interviewbit.com/problems/stringoholics/ InterviewBit problem.

Problem Statement:

You are given an array A consisting of strings made up of the letters ‘a’ and ‘b’ only. Each string goes through a number of operations, where:

  1. At time 1, you circularly rotate each string by 1 letter.
  2. At time 2, you circularly rotate the new rotated strings by 2 letters.
  3. At time 3, you circularly rotate the new rotated strings by 3 letters.
  4. At time i, you circularly rotate the new rotated strings by i % length(string) letters.

Eg: String is "abaa"

  1. At time 1, string is "baaa", as 1 letter is circularly rotated to the back
  2. At time 2, string is "aaba", as 2 letters of the string "baaa" is circularly rotated to the back
  3. At time 3, string is "aaab", as 3 letters of the string "aaba" is circularly rotated to the back
  4. At time 4, string is again "aaab", as 4 letters of the string "aaab" is circularly rotated to the back
  5. At time 5, string is "aaba", as 1 letters of the string "aaab" is circularly rotated to the back

After some units of time, a string becomes equal to it’s original self. Once a string becomes equal to itself, it’s letters start to rotate from the first letter again (process resets). So, if a string takes t time to get back to the original, at time t+1 one letter will be rotated and the string will be it’s original self at 2t time. You have to find the minimum time, where maximum number of strings are equal to their original self. As this time can be very large, give the answer modulo 109+7.

Note: Your solution will run on multiple test cases so do clear global variables after using them.

Input:

A: Array of strings. Output:

Minimum time, where maximum number of strings are equal to their original self. Constraints:

1 <= size(A) <= 10^5 1 <= size of each string in A <= 10^5 Each string consists of only characters 'a' and 'b' Summation of length of all strings <= 10^7

But I got Time Limit Exceed Error.

I followed the below approach:

With respect to a single string, the total number of bits rotated after N operations is 1+2+3+….+N which is (N*(N+1))/2. We get back the original string only when the total number of rotated bits is a multiple of the length of the string S(LEN).

This can be done in O(N) time for each string (Summation of length of all strings is <= 1e6), by finding all (N(N+1))/2 where N starts from 1 and goes upto (2LEN-1).

But there is a catch, this wont always give you the minimum number of operations. Its possible that during rotation, you can get the original string before the number of bits rotated is a multiple of LEN.

Example: S=> 100100 Here, in 2 operations, we get the original string back. This takes place because the string is made up of recurring substrings.

Assume string A to be 100 S => AA Hence, over here our length S of string is the length of recurring substring A, so N*(N+1)/2 should be a multiple of length of A.

Length of recurring substring can easily be found out using KMP algorithm in O(N) time complexity for each string.

Find the minimum number of operations for each string, and take the LCM of all these values to get the answer.

My Solution:

#define MOD 1000000007

int findSmallestString(string A)
{
    int n = A.length();
    vector<int> lps(n + 1, 0);
    int index = 0, i = 1;
    
    while(i < n)
    {
        if(A[index] == A[i])
        {
            lps[i] = index + 1;
            index++;
            i++;
        } else
        {
            if(index != 0)
            {
                index = lps[index - 1];
            } else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    int t1 = lps[n - 1];
    int t2 = n - t1;
    
    if(t1 < t2 || (t1 % t2 != 0)) return n;
    
    return t2;
}

int Solution::solve(vector<string> &A) {
    int n = A.size();
    vector<int> v(n);
    
    for(int i = 0; i < n; i++)
    {
        long long len = findSmallestString(A[i]);
        long long k = 1;
        while(1)
        {
            long long rotates = (k * (k + 1)) / 2;
            if(rotates % len == 0)
            {
                v[i] = k;
                break;
            }
            k++;
        }
    }
    
    long long ans = 1ll;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n && v[i] != 1; j++)
        {
            v[j] = v[j] / __gcd(v[i], v[j]);
        }
        
        ans = ((ans % MOD) * (v[i] % MOD)) % MOD;
    }
    
    return ans;
}

Is there any way to optimize the solution?

\$\endgroup\$
4
  • \$\begingroup\$ Please include the text of the code challenge in the question, links can break. \$\endgroup\$
    – pacmaninbw
    May 6 at 14:50
  • \$\begingroup\$ "its" not "it's" in "it’s original self". "it's" is a contraction for "it is". \$\endgroup\$
    – JDługosz
    Jun 7 at 20:42
  • \$\begingroup\$ @JDlugosz while that is the case the OP was merely quoting the source of the challenge. Perhaps it would be more constructive to contact that organization. \$\endgroup\$ Jun 8 at 5:02
  • \$\begingroup\$ It would be proper to insert ["[sic]"](merriam-webster.com/dictionary/sic) in the quoted passage. \$\endgroup\$
    – JDługosz
    Jun 8 at 13:44
0
\$\begingroup\$

As you got TLA, you (probably) need a better algorithm:

  1. Map from the strings to their periods.

  2. Remove duplicates.

  3. Map from string-periods to transformation-periods modulo 109 + 7.

  4. Determine LCM over them modulo 109 + 7.

Regarding implementation efficiency:

You allocate memory everywhere, for std::string and std::vector. Both are expensive, and also superfluous.

For functions expecting a string, see whether std::string_view will fit the deal. If it does it will even beat std::string const&.

Regarding standard conformance:

__gcd() is an implementation detail of your implementation. Just use std::gcd().

\$\endgroup\$
-1
\$\begingroup\$
#define MOD 1000000007

Don't use #define. This should be

constexpr int MOD = 1000000007;

(and this is assuming that ints are big enough to hold that value!)

int findSmallestString(string A)

Why are you passing A by value, duplicating the string? Write const string& as a matter of course; but use string_view for parameters when that makes sense.

int n = A.length();

You mean size_t, not int. Is this going to change? I think it should not; you should write

const auto n = A.length();

Later, you call it as

long long len = findSmallestString(A[i]);

So is it int or long long? Again, I don't think you are modifying len after this so why isn't it const?


You seem to be missing all the #include statements, and maybe others, so this won't compile as-posted. Please post complete examples.

Where does __gcd come from? That is a reserved name, so I suppose some non-standard built-in.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.