459. Repeated Substring Pattern
Repeated Substring Pattern (LeetCode 459) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Repeated Substring Pattern Detection subpattern.
How to solve Repeated Substring Pattern
Repeated Substring Pattern is a Repeated Substring Pattern Detection problem, part of String Manipulation Patterns. Learn to detect if a string can be constructed by repeating a substring pattern.
Work towards the solution in these steps:
- Think about how you can use string properties to determine if the entire string is made by repeating a smaller substring.
- Consider the lengths of possible substrings that could repeat to form the original string; what constraints do these lengths have relative to the full string length?
- Try checking substrings of the original string that are prefixes and see if repeating them enough times reconstructs the original string.
The reference solution runs in O(n) time and O(n) space.
The Repeated Substring Pattern solution and editorial walks through the full approach with reference code.
Problem statement
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.
Topics and companies
Topics: String, String Matching.
Reported in interviews at Google.
How to practise Repeated Substring Pattern on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Repeated Substring Pattern in the code editor, or read the Repeated Substring Pattern editorial for a worked solution with its approach and complexity analysis.
Where Repeated Substring Pattern sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Repeated Substring Pattern Detection subpattern
- The full DSA patterns sheet
Problems related to Repeated Substring Pattern
Other problems that use the same Repeated Substring Pattern Detection and String Manipulation Patterns techniques:
- Greatest Common Divisor of Strings — Easy, same subpattern
- Add Strings — Easy, same pattern
- Excel Sheet Column Title — Easy, same pattern
- Find Beautiful Indices in the Given Array II — Hard, same pattern
- Find the Index of the First Occurrence in a String — Easy, same pattern
- Integer to Roman — Medium, same pattern
Repeated Substring Pattern FAQ
What is the LeetCode number of Repeated Substring Pattern?
Repeated Substring Pattern is LeetCode problem 459, rated Easy.
What pattern is used to solve Repeated Substring Pattern?
Repeated Substring Pattern is a Repeated Substring Pattern Detection problem. It belongs to the String Manipulation Patterns pattern, in the Repeated Substring Pattern Detection subpattern.
What is the time complexity of Repeated Substring Pattern?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Repeated Substring Pattern?
Repeated Substring Pattern has been reported in interviews at Google.