Java Simple Solution with Explanation


  • 99
    public boolean repeatedSubstringPattern(String str) {
    	int l = str.length();
    	for(int i=l/2;i>=1;i--) {
    		if(l%i==0) {
    			int m = l/i;
    			String subS = str.substring(0,i);
    			StringBuilder sb = new StringBuilder();
    			for(int j=0;j<m;j++) {
    				sb.append(subS);
    			}
    			if(sb.toString().equals(str)) return true;
    		}
    	}
    	return 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

  • 88

    Added a small check in your code and time reduced from 48 ms to 18 ms. Just return if any of the substring will not match. No need to create the whole string.

    public boolean repeatedSubstringPattern(String str) {
            int len = str.length();
        	for(int i=len/2 ; i>=1 ; i--) {
        		if(len%i == 0) {
        			int m = len/i;
        			String subS = str.substring(0,i);
        			int j;
        			for(j=1;j<m;j++) {
        				if(!subS.equals(str.substring(j*i,i+j*i))) break;
        			}
        			if(j==m)
        			    return true;
        		}
        	}
        	return false;
        }

  • 0
    I

    What is the time complexity of this?


  • 0

    @prateek470

    Good improvement!
    Thanks for your contribution prateek470!


  • 2
    V

    @icezhou0784 I beleive it would have to be worst case O(n^2). The worst case scenario for divisor would be n. divisor = len/strpos right? So when strpos = 1, divisor = len/1 => divisor = len. So when divisor == n we have an O(n^2) worst case runtime.


  • 1

    @fabrizio3 Welcome!


  • 0
    I

    @vikram4

    But for the inner loop, it is one and only one time which would happen like what you said. O(n^2) I think would be the worse case that each time happen like this? So I think it the upper bound might be less than that.


  • 0
    V

    @icezhou0784 Even though it is only one time, I think we still have to clasify this algorithm as O(n^2) because there is a set of loop iterations that goes across all O(n^2) elements, i.e. the worst case.


  • 2
    I

    @vikram4
    I think the much tighter bound would be O(N*sqrt(N)). Because we didn't try each possible N in the inner for loop. On the contrary, we try each valid divisor and the number of it is less than O(sqrt(N)). So I think O(N^2) is not tight enough as the time complexity.


  • 1
    V

    @icezhou0784 I understand your point.. But I'm wary to assign a complexity of O(nsqrtn) without a proper mathematical proof for why that might be the case. We can't just guess the time complexity. I can see a clear case for O(n^2) fitting as an upper bound, but I do not see one for O(nsqrtn) personally. If someone can provide a proof or explanation for why I'd be very interested to read.

    Personally I see your point that we have at most sqrt(N) divisors. But I think we also have to consider the max value of one of those divisors in the sqrt(N) possibilities... And the max value of the divisor can be n. So therefore in that worst case scenario where divisor in n, we are running in O(n^2) and thus that is the time complexity because big O notation takes into account the worst case runtime not average. That is my reasoning behind my position.


  • 0
    I

    @vikram4

    I think you might right cause I found "the number of valid divisor is less than O(sqrt(N))" is not always true.


  • 2

    @vikram4
    You are right. Worst case complexity is same O(n^2). But average time complexity will lie between O(n) and O(n^2) as best case complexity is O(n)

    @icezhou0784


  • 20
    L

    @prateek470 @icezhou0784 @vikram4
    The number of factors is always bounded by O(sqrt(n)). Factors come in pairs, i.e., n = a * b. The smaller one of a and b must be no larger than sqrt(n); otherwise, we have a > sqrt(n) and b > sqrt(n) and thus a * b > n. Therefore, there are at most 2sqrt(n) = O(sqrt(n)) factors, and the worst case runtime for this algorithm is O(n^1.5).


  • 0
    I

    @lixx2100

    Nice explanation!


  • 0
    V

    @lixx2100 Thanks for the explanation, it's helping clear things up. For clarification does it boil down to O(numFactors*largestDivisor) where:
    numFactors = sqrt(n)
    largestDivisor = n
    ====> O(n^1.5)
    For worst case runtime?


  • 1
    V
    This post is deleted!

  • 0
    B

    @prateek470 nice optimiztion, since that it is cost too much to create a new string,thx


  • 0

    Thanks @bwju


  • 0
    H

    Same idea, but use a HashSet instead of String.equals()

    public boolean repeatedSubstringPattern(String str) {
        if (str == null || str.length() == 0) {
            return false;
        }
        
        int len = str.length();
        
        for (int l = len / 2; l >= 1; l --) { // len of substrings
            if (len % l != 0) { // str cannot be divided into substrings with same length l
                continue;
            }
            Set<String> set = new HashSet<>();
            int i;
            for (i = 0; i < len / l; i ++) {
                String substr = str.substring(i * l, (i + 1) * l);
                if (!set.isEmpty() & set.add(substr)) break;
            }
            if (i == len / l) return true;
        }
        return false;
    }

  • 5
    Z

    similar idea but use method String.indexOf()

    public boolean repeatedSubstringPattern(String str) {
            for(int i=str.length()/2;i>=1;i--){
                if(str.length()%i==0){
                    int j=i;
                    String sub=str.substring(0,j);
                    while(str.indexOf(sub,j)==j)j+=i;
                    if(j==str.length())return true;
                }
            }
            return false;
        }
    

Log in to reply
 

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