LeetCode 459: Repeated Substring Pattern Solution
Master LeetCode problem 459 (Repeated Substring Pattern), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
459. Repeated Substring Pattern
Problem Explanation
Explanation
To solve this problem, we can iterate over all possible substrings of the input string s. For each substring, we check if repeating it multiple times can reconstruct the original string s. We can do this by checking if the length of s is divisible by the length of the current substring, and if the concatenation of the substring repeated multiple times equals s.
If such a substring is found, we return true. If no such substring exists, we return false.
- Time complexity: O(n^2) where n is the length of the input string
s - Space complexity: O(n) for storing the substrings
Solution Code
class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
for (int i = 1; i <= n/2; i++) {
if (n % i == 0) {
String sub = s.substring(0, i);
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n/i; j++) {
sb.append(sub);
}
if (sb.toString().equals(s)) {
return true;
}
}
}
return false;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 459 (Repeated Substring Pattern)?
This page provides optimized solutions for LeetCode problem 459 (Repeated Substring Pattern) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 459 (Repeated Substring Pattern)?
The time complexity for LeetCode 459 (Repeated Substring Pattern) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 459 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 459 in Java, C++, or Python.