Periodic String

Easy
0/40
Average time to solve is 15m
profile
Contributed by
17 upvotes
Asked in companies
FacebookMAQ Software

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
xxxxxx
aabbaaabba
abcba
Sample Output 1:
True
True
False
Explanation of sample input 1 :
Test Case 1:
In the first test case, we can clearly see that the string has a repeating string ‘x’ 6 times. So we return true

Test Case 2:

In the second test case, we can see that the string ‘aabba’ repeats twice to form the given string. Hence we return true,

Test Case 3:

In the third test case, we can see that there is no string which repeats itself to form the given string, hence we return false.
Sample Input 2:
2
vwvnqpnchqik
ubzumubzumubzumubzum
Sample Output 2:
False
True
Hint

SImply brute force the solution

Approaches (2)
Brute force
  • 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.
Time Complexity

O(N), Where ‘N’ size of the string

 

We need to check for equality of string and also concatenate string which takes O(N) time.

Space Complexity

O(N), where ‘N’ is the size of the string.

 

We need to make a new string to compare it with the older one which takes o(N) space.

Code Solution
(100% EXP penalty)
Periodic String
Full screen
Console