Stringoholics

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.

A: Array of strings.

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

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

A: [a,ababa,aba]

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.

Method:

First, for each string, we find the minimum number of rotations required for it to become itself. Then we can calculate the number of times (defined by this problem statement) we need to rotate the array. Then we can calculate the least common multiple for all the number of times required.

Solution:

n = size of array
m = max length of string
Time: O(n*m*log(m))
Space: O(m)

import java.math.BigInteger;

public class Solution {
    private BigInteger gcd(BigInteger a, BigInteger b) {
        if (a.compareTo(b) < 0) {
            return gcd(b, a);
        }
        if (b.equals(BigInteger.ZERO)) return a;
        return gcd(b, a.mod(b));
    }
    
    private BigInteger lcm(BigInteger a, BigInteger b) {
        return (a.multiply(b)).divide(gcd(a, b));
    }
    
    private long minNumberOfRotation(String str) {
        // long count = 1;
        String two = str + str;
        return two.indexOf(str, 1);
        // for (int i = 1; i < str.length(); i ++) {
        //     if (two.substring(i, i + str.length()).equals(str)) {
        //         return count;
        //     }
        //     count ++;
        // }
        // return count;
    }
    
    public int solve(ArrayList<String> A) {
        BigInteger max = BigInteger.ONE;
        for (String s : A) {
            long numberOfRotation = minNumberOfRotation(s);
            for (long i = 1; i <= 2 * numberOfRotation + 1; i ++) {
                if ((i * (i + 1) / 2) % numberOfRotation == 0) {
                    max = lcm(max, new BigInteger(String.valueOf(i)));
                    break;
                }
            }
        }
        return max.mod(new BigInteger("1000000007")).intValue();
    }
}