Leetcode 459. Repeated Substring Pattern

Problem Explanation:

This problem involves verifying whether a given string can be constructed by repeating a pattern substring within it. If such a substring can be found and the parent string can be completely constructed by repeating this substring, then we return True, otherwise return False.

For example, if the input string is 'abab', we can consider 'ab' as a repeating pattern and therefore, the output would be True. But if the input string is 'abcabcab', no repeating pattern can completely construct the input string, and hence, the output would be False.

Approach to the Solution:

The approach is intuitive. We take the input string and append it to itself. We then remove the first and last characters and then check if the original string exists in this doubled string. If it exists, that means there is a repeating pattern in the original string, hence, we return True. If it doesn't, that means no repeating pattern exists and we return False.

This is a simple string manipulation algorithm, it checks if the original string is a substring of the concatenated string.

Solution:

C++:

1
2cpp
3class Solution {
4 public:
5  bool repeatedSubstringPattern(string s) {
6    // Concatenating the input string
7    string ss = s + s;
8    
9    // Checking if the input string exists in the concatenated string (without the first and last character)
10    return ss.substr(1, ss.length() - 2).find(s) != string::npos;
11  }
12};

Java :

1
2java
3public class Solution {
4        public boolean repeatedSubstringPattern(String str) {
5            String s = str + str;
6            //return concatenated string without first and last character contains original string
7            return s.substring(1, s.length() - 1).contains(str);
8        }
9}

Python:

1
2python
3class Solution:
4    def repeatedSubstringPattern(self, s):
5        return s in (s + s)[1: -1]

JavaScript:

1
2javascript
3var repeatedSubstringPattern = function(s) {
4    return (s + s).slice(1, -1).includes(s);
5};

Conclusion:

In this problem, we understood how to find a repeating pattern in a string. The solutions provided here are for Python, Java, C++ and JavaScript languages. By concatenating the string, removing the first and last characters, and checking if the original string is a substring of this modified string, we can determine whether a repeating pattern exists.This simple string manipulation can be applied to not only strings but also related sequences in other domains, such as musical rhythm, DNA sequences, and regular expressions. The time complexity of the solution is O(n), where n is the length of the string, making it extremely efficient.

Although the algorithm is quite straightforward, it's essential to understand the logic behind appending the string to itself and removing the first and last characters. This approach ensures we are considering all possible patterns in the string instead of just arbitrarily dividing it based on length.

In real-world applications, such a pattern-checking algorithm can be useful in data validation, information retrieval, cryptography, and even in the field of bioinformatics for pattern recognition in DNA sequencing.

No matter what programming language you prefer - C++, Java, Python, or Javascript - the concept remains the same. The solution demonstrates how this problem can be solved with a single line of code in each language, emphasizing the elegance and efficiency of the proposed algorithm. Happy Coding!