How do I check if a string is entirely made of the same substring?
I have to create a function which takes a string, and it should return true or false based on whether the input consists of a repeated character sequence. The length of the given string is always greater than 1 and the character sequence must have at least one repetition.
"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")
"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)
I have created the below function:
Checking of this is part of the real problem. I can't afford a non-efficient solution like this. First of all, it's looping through half of the string.
The second problem is that it is using replace() in each loop which makes it slow. Is there a better solution regarding performance?
Answer
There’s a nifty little theorem about strings like these.
A string consists of the same pattern repeated multiple times if and only if the string is a nontrivial rotation of itself.
Here, a rotation means deleting some number of characters from the front of the string and moving them to the back. For example, the string hello could be rotated to form any of these strings:
hello (the trivial rotation)
elloh
llohe
lohel
ohell
To see why this works, first, assume that a string consists of k repeated copies of a string w. Then deleting the first copy of the repeated pattern (w) from the front of the string and tacking it onto the back will give back the same string. The reverse direction is a bit trickier to prove, but the idea is that if you rotate a string and get back what you started with, you can apply that rotation repeatedly to tile the string with multiple copies of the same pattern (that pattern being the string you needed to move to the end to do the rotation).
Now the question is how to check whether this is the case. For that, there’s another beautiful theorem we can use:
If x and y are strings of the same length, then x is a rotation of y if and only if x is a substring of yy.
As an example, we can see that lohel is a rotation of hello as follows:
hellohello
^^^^^
In our case, we know that every string x will always be a substring of xx (it’ll appear twice, once at each copy of x). So basically we just need to check if our string x is a substring of xx without allowing it to match at the first or halfway character. Here’s a one-liner for that:
function check(str) {
return (str + str).indexOf(str, 1) !== str.length;
}
Assuming indexOf is implemented using a fast string matching algorithm, this will run in time O(n), where n is the length of the input string.
Hope this helps!