Find a Repeated Substring Pattern in a given string

Question

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1: Input: "abab"

Output: True

Explanation: It's the substring "ab" twice. Example 2: Input: "aba"

Output: False Example 3: Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

I found the above question on a online programming site here. I submitted the following answer which is working for the custom test cases, but is getting time exceed exception on submission. I tried other way of regex pattern matching, but as expected, that should be taking more time than this way, and fails too.

public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        int substringEndIndex = -1;
        int i = 0;
        char startOfString = str.charAt(0);
        i++;
        char ch;
        while(i < str.length()){
            if((ch=str.charAt(i)) != startOfString){
                //create a substring until the char at start of string is encountered 
                i++;
            }else{
                if(str.split(str.substring(0,i)).length == 0){
                    return true;
                }else{
                    //false alarm. continue matching.
                    i++;
                }
            }
        }
        return false;
    }
}

Any idea on where I am taking too much time.

Answer 1

Ther's a literally one-line solution to the problem. Repeat the given string twice and remove the first and last character of the newly created string, check if a given string is a substring of the newly created string.

def repeatedSubstringPattern(self, s: str) -> bool:
     return s in (s + s )[1: -1]

Eg:

1. str: abab. Repeat str: abababab. Remove the first and last characters: bababa. Check if abab is a substring of bababa.
2. str: aba. Repeat str: abaaba Remove first and last characters: baab. Check if aba is a substring of baab.

Mathematical Proof:

Let P be the pattern that is repeated K times in a string S.

S = P*K.

Let N be the newly created string by repeating string S

N = S+S.

Let F be the first character of string N and L be the last character of string N

N = ( F+ P*(K-1) )+ (P*(K-1) + L)

N = F+ P(2K-2)+ L

If K = 1. i.e a string repeated only once

N = F+L. //as N != S So False

If K ≥ 2.

N = F+k'+ N

Where k'≥K. As our S=P*K. So, S must be in N.

We can further use KMP algorithm to check if S is a sub-string of N. Which will give us time complexity of O(n)