Java solution O(n) with explaination


  • 0
    C

    Reference taken from http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/

        public boolean repeatedSubstringPattern(String str) {
            // first we need to perform KMP search to find the longest common prefix and suffix.
            int[] arr = new int[str.length()];
    
            int i = 1, j = 0;
    
            while (i < str.length()) {
                if (str.charAt(i) == str.charAt(j)) {
                    arr[i] = j + 1;
                    j++;
                    i++;
                } else if (j > 0) {
                    j = arr[j - 1];
                } else {
                    i++;
                }
            }
    
            // taking the maximum prefix length
            int prefixLength = arr[arr.length - 1];
    
            // this should be true if these two condition holds. 
            // 1. ther string has a common prefix and suffix greater than zero. e.g. ABCABC where prefix is ABC abd suffix is ABC
            // 2. if there is an overlap of prefix and suffix then len - prefix should divide the len. 
            // e.g str = ABCABCABC --- here common prefix is 1 to 6 and common suffix is 4 to 9. Since there is an overlap if we substract 
            // suffix from length we are left with 9 - 6 = 3 which divides 9.
            return prefixLength > 0 && str.length() % (str.length() - prefixLength) == 0;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.