Stringoholics InterviewBit Solution

Problem: Stringoholics

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:

After some units of time, a string becomes equal to its 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 its original self at 2t time. You have to find the minimum time, where the 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

Example:

Input

A: [a,ababa,aba] 

Output

4

String 'a' is it's original self at time 1, 2, 3 and 4.
String 'ababa' is it's original self only at time 4. (ababa => babaa => baaba => babaa => ababa)
String 'aba' is it's original self at time 2 and 4. (aba => baa => aba)

Hence, 3 strings are their original self at time 4.

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 it will always not gives the minimum number of operations, as a string can be a repetitive string.

For example: S = "abbabbabbabb"
Length(S) = 12, but we don't need to take the length as 12 as to get minimum number of operations, we must have to take 3.

Because string "abbabbabbabb" can be produced from string "abb".
Suppose A = "abb"
Then, S = AAAA
And, Length(A) = 3.

The above can be found using lps array, which we have used in KMP algorithm.

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

Time & Space Complexity

Time Complexity: O(M)

- Here M is the sum of all the strings given.

Space Complexity: O(N)

Solution

Code in C++:

Note: The complexity to find LCM in the last step for the above algorithm is O(N^2). But still, it will not give TLE, since the test cases are weak.

To avoid this you can compute LCM using a different approach, we are not adding it here since giving too much info in the same place will increase confusion in understanding the solution.

You can refer to this on how to find LCM of an array with modulo in O(NlogN).