Root The String

Moderate

0/80

Average time to solve is 20m

Contributed by

3 upvotes

Asked in company

Problem statement

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”.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input-1

2
3
aba
4
aaaa

Sample Output-1

1
4

Explanation for Sample Input 1:

For test case 1:
    The given string does not have any root greater than 1. Hence the answer is 1.
For test case 2:
    We can take ‘N’ = 4 and get ‘T’ = ‘a’. There is no other value of ‘N’, which is greater than 4. Hence the answer is 4.

Sample Input -2

2
6
abcabc
2
zz

Sample Output -2

2
2

Hint 1

Hint 2

Which numbers are the candidate for the answer?

Approaches (2)

Approach 1

Approach 2

Maths

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.
Print ‘ans’.

Time Complexity

O(N * number_of_divisors_of_N), Where 'N' is the length of the string.

For each divisor, we are comparing two strings of length ‘N’. Hence the overall complexity is O(N * number_of_divisors_of_N).

Space Complexity

O(N), Where 'N' is the length of the string..

For each divisor, we are constructing a string of length ‘N’. Since only one instance is maintained at any time, the overall complexity is O(N).

(100% EXP penalty)

Root The String

Console