DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Repeated Substring Pattern

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example 1:

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

Example 2:

Input: s = "aba"
Output: false

Example 3:

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

SOLUTION:

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for l in range(1, 1 + (n // 2)):
            valid = True
            prev = None
            for i in range(0, n, l):
                if prev and prev != s[i:i+l]:
                    valid = False
                    break
                prev = s[i:i+l]
            if valid:
                return True
        return False
Enter fullscreen mode Exit fullscreen mode

Top comments (0)