Leetcode – Repeated Substring Pattern Solution in Python

Spread the love

String manipulation is a common theme in coding interviews and competitive programming. In this article, we delve into a particular string problem from Leetcode named “Repeated Substring Pattern”. We will explore various solutions to this problem using Python and analyze the efficiency in terms of time and space complexity.

Table of Contents

  1. Problem Statement and Understanding
  2. Approach 1: Naive Approach
  3. Approach 2: Using KMP Algorithm
  4. Approach 3: String Concatenation Trick
  5. Time and Space Complexity Analysis
  6. Practical Use-Cases
  7. Conclusion

1. Problem Statement and Understanding

Problem Statement

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:

Input: "abab"

Output: True

Explanation: It’s the substring “ab” twice.

Understanding the Problem

We are given a string s, and we need to determine if s can be represented as n repetitions of some substring, where n is greater than 1.

2. Approach 1: Naive Approach

We can start by iterating through all possible substring lengths. For each length, we can check if the string can be divided into substrings of that length without any remainder characters, and if the concatenated substring equals the original string.

def repeatedSubstringPattern(s):
    n = len(s)
    
    # Check every substring length from 1 to n / 2
    for i in range(1, n // 2 + 1):
        # If n is divisible by i
        if n % i == 0:
            # Build the substring by repeating it n / i times
            substring = s[:i] * (n // i)
            # Check if the concatenated substring equals the original string
            if substring == s:
                return True
                
    return False

3. Approach 2: Using KMP Algorithm

The Knuth-Morris-Pratt (KMP) algorithm is used for pattern searching within strings. It can also be utilized to find the length of the longest proper prefix that is also a suffix. This information can be used to solve this problem efficiently.

def repeatedSubstringPattern(s):
    n = len(s)
    # LPS array for KMP algorithm
    lps = [0] * n
    j = 0
    
    # Build LPS array
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = lps[j-1]
        if s[i] == s[j]:
            j += 1
            lps[i] = j
    
    # Length of the longest proper prefix that is also a suffix
    length = lps[-1]
    
    # Check if the string can be represented by repeated substrings
    return length > 0 and n % (n - length) == 0

4. Approach 3: String Concatenation Trick

An interesting trick is to concatenate the string to itself, remove the first and last characters, and check if the original string is present in the concatenated string.

def repeatedSubstringPattern(s):
    return s in (s + s)[1:-1]

5. Time and Space Complexity Analysis

  • Approach 1: This approach has a time complexity of O(n^2) and a space complexity of O(n).
  • Approach 2: The KMP-based approach has a time complexity of O(n) and a space complexity of O(n) to store the LPS array.
  • Approach 3: The string concatenation trick has a time complexity of O(n) and a space complexity of O(n) because it creates a new concatenated string.

6. Practical Use-Cases

Identifying repeated patterns in strings can have applications in various domains such as data compression, DNA sequencing, and plagiarism detection.

7. Conclusion

In this article, we explored different approaches to solving the “Repeated Substring Pattern” problem on Leetcode using Python. Understanding the KMP algorithm can be particularly beneficial not only for this problem but also for other string manipulation problems. The string concatenation trick showcases how sometimes a simple and clever idea can lead to an elegant and efficient solution.

Leave a Reply