Last Updated: 25 Nov, 2021
Root The String
Moderate
Asked in company
Let's say a string ‘T’ to be the ‘Xth’ root of a string ‘S’ if you can concatenate a string ‘T’ a total of ‘X’ times and get the string ‘S’ as a result.
You have a string ‘S’ of length ‘N’ consisting only of lowercase English alphabets. You have to find the maximum value of ‘X’, such that the ‘Xth’ root of the string exists.
For example: If S = “abcabc”, then for ‘X’ = 1, the string ‘T’ will be “abcabc”, and for ‘X’ = 2, the string ‘T’ will be “abc”.
Input Format-
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer, ‘N’, denoting the length of the input string S.
The following line contains the string ‘S’ of length ‘N’.
Output Format-
For each test case, you have to print an integer denoting the minimum number of operations required to form the given string ‘S’.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints -
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
Note- Sum of ‘N’ over all test cases does not exceed 10^5.
Time Limit: 1 sec
Approaches
Approach: Only N’s divisors can be a valid answer because ‘N’ = length(T) * X. We will check for all the divisors and print the maximum divisor that is a root of the string ‘S’.
Algorithm:
- Create a variable ‘ans’ and initialize it to 1.
- Iterate using a for loop from i = ‘1’ to ‘N’.
- If ‘i’ is a divisor of ‘N’.
- Create a string ‘new_string’ by concatenating S[0…(i - 1)] a total of (N / i) times.
- If S == new_string.
- Update ‘ans’ to (N / i).
- Break.
- If ‘i’ is a divisor of ‘N’.
- Print ‘ans’.
Prerequisite: Z - Algorithm
Approach: Let’s say ‘X’ is the answer for a string ‘S’ of length ‘N’, then the length of the string ‘T’, let’s say ‘Y’ will be (N / X). Also, S[0…(N - 1 - Y)] will be equal to S[Y….(N - 1)] as S = ‘T’ * X (i.e. the string ‘T’ is repeated ‘X’ times so the first (X - 1) * ‘Y’ characters will be equal to the last (X - 1) * ‘Y’ characters). So we have to find the largest suffix of the string ‘S’, which is also a prefix of the string ‘S’. We can find this using the Z - Algorithm. Then we can find ‘Y’ and then the ‘X’ using some basic algebra.
Algorithm:
- Func z_function().
- Create two variables, ‘L’, ‘R’ and initialize both of them to 0.
- Create an array ‘Z’ of length ‘N’.
- Iterate using a for loop from i = ‘1’ to ‘N - 1’.
- If ‘i’ <= ‘R’.
- Update Z[i] to min (R - i + 1, Z[i - L]).
- while (i + Z[i] < N) and (S[Z[i]] == S[i + Z[i]]).
- Increment Z[i] by 1.
- If i + Z[i] - 1 > R.
- Update L to i.
- Update R to i + Z[i] - 1.
- If ‘i’ <= ‘R’.
- Return Z.
- Func Main().
- Create a variable ‘ans’ and initialize it to 1.
- Use z_function() to get the ‘Z’ array.
- Iterate using a for loop from i = ‘1’ to ‘N - 1’.
- If Z[i] == N - i.
- If ‘N’ is divisible by ‘i’.
- Update ‘ans’ to max(ans, N / i).
- If ‘N’ is divisible by ‘i’.
- If Z[i] == N - i.
- Print ‘ans’.