This problem is really tough. Its difficulty level is so high. I ave been stuck on this problem from past few days. I have accessed the solution approach as well, implemented KMP, LCM and still unable to pass test cases. My code is not getting submitted and I need to start with the next topic on next level linked lists. It would be great help if someone could me to know how to find the minimum number of operations for each string and Handling of overflow for LCM should be handled by breaking the number down into factors, or please add some more problems to this bucket, or remove this problem until it is improved. Thanks!
- Check again the first two paragraphs of the solution approach. They are actually giving a formula to calculate the amount of characters rotated at a given time. Then you verify if the total of rotated chars is multiple of the length.
- It might happen the input string is made up of recurring substrings and therefore the length for comparison must be the one of the recurring substring. Use the prefix array described in the KMP to find out if that is the case. Just verify if there is a suffix with half length of the string which is also a prefix of the string.
- By using the LCM approach with factorized numbers you will be able to keep the calculation under the 10^9 + 7 limit during multiplications.
You can also find the length of recurring sub-string using brute force in O(nlogn) as the length of recurring sub-string will always be a divisor of n(string size) and a number can have at max logn divisors.Therefore brute force will work in O(nlogn) where n is for checking if its possible to do so for a particular divisor(i) i.e str[i] is equal to str[i-divisor(i)] for all i in string.
This is a math problem, not a string problem.