Repeated Substring Pattern LeetCode Solution

Difficulty Level Easy
Frequently asked in Amazon Facebook Google SalesforceViews 6663

Problem Statement

Repeated Substring Pattern LeetCode Solution – Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Explanation

  1. The first char of input string is the first char of repeated substring
  2. The last char of input string is the last char of repeated substring
  3. Let S1 = S + S (where S in input string)
  4. Remove 1 and last char of S1. Let this be S2
  5. If S exists in S2 then return true else false
  6. Let i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]

Observations :

1. The substring that will be repeated should repeat at least 2 times otherwise every string will be considered as a repeated substring.
2. Since the number of repetitions is between n times (size of the string) to 2 times so the size of a valid repeating substring would lie between    [ 1, n / 2 ].
3. A substring of size ” i ” will only be a repeated substring if size % i == 0.
4. Now following which we have two methods whether current substring of size suppose k is a repeated substring or not:-

Approach A :

  1. Run a loop from i = 1 to i = n/2.
  2. For each value ” i ” we can store curr substring as 0 to i and initialize a variable j = i.
  3. Now while (j<s.length() && substring(j,j+i)==curr) j+=i;
  4. if j==s.length() return true // we reached the end of the string while adding.
  5. return false // no size substring fitted the condition.

Approach B :

Instead of checking every substring in step 3, we will create a new string considering the repeated substring s.length() / i times.

 

Code

C++ Code for Repeated Substring Pattern

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        
        string ans="",temp="",res="";
        
        for(int i=0;i<s.length()-1;i++)
        {
            temp+=s[i];
            if(s.length()%temp.length()==0)
            {
                res="";
                for(int j=1;j<=int(s.length()/temp.length());j++)
                    res+=temp;
                if(res==s)
                    return 1;
            }
            
        }
            
        return 0;
    }
};

Python Code for Repeated Substring Pattern

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        
        ans=""
        temp=""
        
        for i in range(0,len(s)-1):
            temp+=s[i]
            if  len(s)%len(temp)==0 and temp*int((len(s)/len(temp)))==s:
                print(temp)
                return 1
        
        return 0

Java Code for Repeated Substring Pattern

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        for (int size=1;size<=s.length()/2;size++) {
            if (s.length()%size==0) {
                String curr=s.substring(0,size);
                int j=size;
                while (j<s.length() && s.substring(j,j+size).equals(curr)) {
                    j+=size;
                }
                if (j==s.length()) return true;
            }
        }
        return false;
        
    }
}

Complexity Analysis for Repeated Substring Pattern LeetCode Solution

Time Complexity: O(n^2)

Space Complexity: O(1)

Reference: https://en.wikipedia.org/wiki/Substring

Translate »