In this guide, you will get 459. Repeated Substring Pattern LeetCode Solution with the best time and space complexity. The solution to Repeated Substring Pattern problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
459. Repeated Substring Pattern LeetCode Solution in C++
class Solution {
public:
bool repeatedSubstringPattern(string s) {
const string ss = s + s;
return ss.substr(1, ss.length() - 2).find(s) != string::npos;
}
}; /* code provided by PROGIEZ */
459. Repeated Substring Pattern LeetCode Solution in Java
class Solution {
public boolean repeatedSubstringPattern(String s) {
final String ss = s + s;
return ss.substring(1, ss.length() - 1).contains(s);
}
} // code provided by PROGIEZ
459. Repeated Substring Pattern LeetCode Solution in Python
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
return s in (s + s)[1:-1] # code by PROGIEZ
