459. Repeated Substring Pattern (Easy)

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

4 solutions from intuitive-but-slow to really-fast-but-a-little-hard-to-comprehend.

Solution 1: Brute Force 188ms

Time Complexity: $$O(n^2)$$

Let us start with the very naive solution. It uses 188 ms to solve 100 test cases. The idea is that when we see a character in str that matches the very first character of str, we can start to hoping that str is a built by copies of the substring composed by all characters before the reappearance of the its first character.

public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        int l = str.length();
        if(l == 1) {
            return false;
        }
        StringBuilder sb = new StringBuilder();
        char first = str.charAt(0);
        sb.append(first);
        int i = 1;
        while(i <= l / 2) {
            char c = str.charAt(i++);
            if(c == first && isCopies(str, sb.toString())) {
                return true;
            }else {
                sb.append(c);
            }
        }
        return false;
    }
    private boolean isCopies(String str, String substr) {
        if(str.length() % substr.length() != 0) {
            return false;
        }
        for(int i = substr.length(); i < str.length(); i += substr.length()){
            if(!str.substring(i).startsWith(substr)){
                return false;
            }
        }
        return true;
    }
}

Solution 2: Brute Force without KMP

Time Complexity: $$O(n^2)$$ 46ms

这道题给了我们一个字符串，问其是否能拆成n个重复的子串。那么既然能拆分成多个子串，那么每个子串的长度肯定不能大于原字符串长度的一半，那么我们可以从原字符串长度的一半遍历到1，如果当前长度能被总长度整除，说明可以分成若干个子字符串，我们将这些子字符串拼接起来看跟原字符串是否相等。 如果拆完了都不相等，返回false。

1. The length of the repeating substring must be a divisor of the length of the input string
2. Search for all possible divisor of str.length, starting for length/2
3. If i is a divisor of length, repeat the substring from 0 to i the number of times i is contained in s.length
4. If the repeated substring is equals to the input str return true

bool repeatedSubstringPattern(string str) {
    int n = str.size();

    for (int i = n/2; i >= 1; --i) {
        if (n%i == 0) {
            int cnt = n/i;
            string t;
            for (int j = 0; j < cnt; ++j) {
                t += str.substr(0, i);
            }
            if (t == str) return true;
        }
    }
    return false;
}

improved version: 29ms

bool repeatedSubstringPattern(string str) {
    int n = str.size();

    for (int i = n/2; i >= 1; --i) {
        if (n%i == 0) {
            int j = i;
            string p = str.substr(0, i);

            while (j < n) {
               if (str.substr(j, i) != p) break;
               j += i;
            }
            if (j == n) return true;
        }
    }
    return false;
}

Solution 3: KMP

Time Complexity: $$O(n)$$ 36 ms

最后一个数字不能为0, 说明有P[n-1]长度的prefix跟suffix相同; 还要满足P[n-1] % (n - P[n-1]) == 0才行，因为n - P[n-1]是一个子字符串的长度，那么重复字符串的长度和肯定是一个子字符串的整数倍，参见代码如下：

True:
    a b c a b c a b c
    0 0 0 1 2 3 4 5 6

True:
    a b c a a b c a a b c a
    0 0 0 1 1 2 3 4 5 6 7 8

bool repeatedSubstringPattern(string str) {
    int n = str.size(), j = 0, P[n];
    P[0] = 0;
    // KMP
    for (int i = 1; i < n; ++i) {
        while (j > 0 && str[j] != str[i]) j = P[j-1];
        if (str[j] == str[i]) ++j;
        P[i] = j;
    }
    j = P[n-1];
    return (j && n%(n-j)==0);
}

Solution 4: KMP idea + solution 2 29ms

Want clearer code that runs even faster ? Here is it. The idea is stated at the end of the explanation for solution 2. Without really find the longest proper prefix that is also a suffix as in solution 3: KMP and see whether the three properties are matched, we just test each remainderStr, from the longest possible that satisfies condition 1 and 2, that whether the corresponding prefix and suffix match each other. It solve 100 test cases in 16ms. So maybe now, you really want to prove the statement since it lead to such a clean and fast solution? It is not hard to prove by induction.

bool repeatedSubstringPattern(string str) {
    int n = str.size();

    for (int i = (n+1)/2; i < n; ++i) {
        if (n%(n-i) == 0) {
            string prefix = str.substr(0,i);
            string remainder = str.substr(i); // substr
            string suffix = str.substr(n-i);
            if (str.substr(0,n-i) == remainder && suffix == prefix) return true;
        }
    }
    return false;
}