Periodic String

Posted: 15 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1
  • 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.
Try Problem