Last Updated: 15 Jan, 2021
Periodic String
Easy
Asked in companies
Given a string ‘S’ find whether the given string is periodic or not.
A string is said to be periodic if it repeats itself after a certain number of characters and the period of repetition is less than the size of the string.
For example: Let ‘S’ be “ababab” we can clearly see that this string is periodic as ‘ab’ is repeated 3 times to make the string ‘S’.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
The first line of each test case contains a string ‘S’ for which we need to find if a given string is periodic or not
Output Format
For each test case, return true if the given string is periodic and return false if the given string is not periodic.
Output for each test case must be in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1<= S.length<=10^5
Where 'S.length' denotes the length of string ‘S’.
The given string consists of lowercase English alphabets only.
Time limit: 1 sec
Approaches
- The key idea is that if the string is made up of repeated strings, the repeated string length must be a factor of ‘S.length’
- So we try all possible factors of s.length and take a substring of 'S' of the size of a factor of 'S' and repeat it.
- If the final string matches 'S' we return true else we return false.
Keeping the above example in mind, we can write the following solution:
- If the length of 'S' is 1 we return false as a string of length 1 can’t have repetition.
- Otherwise, we first check for strings of all the same characters i.e ‘aaaaa’ ‘bbbb’ etc . If we find such a string we return true.
- For all other cases, We simply find all the factors of s.length using a loop and store in an array ‘FACTORS’.
- Once we have the 'FACTORS' array, we define ‘K’ as ‘S’.length/'FACTORS'[i].
- We take a substring of 'S' from the start of size 'FACTORS'[i] and concatenate it ‘K’ times.
- If the resultant string is the same as 'S' we return true else we return false.
- The key idea here is to double the string, that is, append the string to itself. In this way, the pattern would be duplicated.
- On removing the first and the last characters, if there exists some pattern, we would still be able to find the original string somewhere in the middle, taking some characters from the first half and some from the second half.
- Assume 'S' is a periodic string that consists of 'N' repeated sections 'R'.
- (If 'S' = "xyzxyz", then 'N' = 2 and 'R' = "xyz")
- Known
- 'S' = 'N' * 'R'
- 'T' = ('S' + 'S' without first and last chars), in other words, the first 'R' and last 'R' are broken.
- Hence, 'T' = 'S' + 'S' - 2'R' = 'N' * 'R' + 'N' * 'R' - 2'R' = (2'N' - 2) * 'R'
- In order for 'S' to be a substring of 'T', 'T' has to be greater or equal to 'S'
- 'T' >= 'S' , replace 'T' and 'S' by 'N' and 'R'.
- (2'N' - 2) * 'R' >= 'N' * 'R', eliminate 'R' on both sides
- 2'N' - 2 >= 'N', solve the formula
- 'N' >= 2
- In other words, in order for 'S' to be a substring of 'T', the repetition 'N' >= 2.
- Therefore, 'S' = 'N' * 'R' >= 2 * 'R', which implies that the pattern 'R' repeats over twice in 'S'.
- So now all we need to do is to find that if 'S' is a substring of 'T'
Keeping in mind the above idea, we can use the following approach:
- Make a string ‘T’ by concatenating the string ‘s’ to itself and removing the first and last character of s+s.
- Simply find if ‘S’ is a substring of ‘T’ using find() function.