What is the time complexity of Repeated Substring Pattern?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Repeated Substring Pattern?

This problem uses String, String Matching. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Repeated Substring Pattern?

Insight 1: If a string `s` is formed by repeating a substring, then the length of the substring must be a divisor of the length of `s`. This is because the substring must fit an integer number of times within `s`. Insight 2: We can iterate through all possible substring lengths that are divisors of the string's length. For each possible length, we extract the substring and check if repeating it generates the original string.

Which companies ask LeetCode 459. Repeated Substring Pattern in interviews?

This problem is frequently asked at Myntra.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Repeated Substring Pattern - LeetCode 459 Solution

Q: How to solve Repeated Substring Pattern?

The solution iterates through all possible lengths of the repeating substring, starting from 1 up to half the length of the original string. For each length, it checks if it's a divisor of the original string's length. If it is, it extracts the substring of that length from the beginning of the string and then constructs a new string by repeating this substring. Finally, it compares the constructed string with the original string. If they are equal, it means the original string can be formed by repeating the substring, so the function returns `true`. If no such substring is found after iterating through all possible lengths, the function returns `false`.

Repeated Substring Pattern - Complete Solution Guide

Repeated Substring Pattern is LeetCode problem 459, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 <= 10 4 s consists of lowercase English letters.

Detailed Explanation

The problem asks us to determine if a given string `s` can be formed by repeating a substring of itself. In other words, we need to find a substring `sub` such that concatenating `sub` multiple times results in the original string `s`. The input is a string `s` consisting of lowercase English letters, with a length between 1 and 10,000. The output is a boolean value: `true` if `s` can be formed by repeating a substring, and `false` otherwise.

Solution Approach

The solution iterates through all possible lengths of the repeating substring, starting from 1 up to half the length of the original string. For each length, it checks if it's a divisor of the original string's length. If it is, it extracts the substring of that length from the beginning of the string and then constructs a new string by repeating this substring. Finally, it compares the constructed string with the original string. If they are equal, it means the original string can be formed by repeating the substring, so the function returns `true`. If no such substring is found after iterating through all possible lengths, the function returns `false`.

Step-by-Step Algorithm

Step 1: Get the length `n` of the input string `s`.
Step 2: Iterate from `i = 1` to `n // 2` (inclusive). This loop represents the possible lengths of the repeating substring.
Step 3: Inside the loop, check if `n` is divisible by `i` (i.e., `n % i == 0`). If it is, it means `i` could be the length of the repeating substring.
Step 4: If `n % i == 0`, extract the substring `sub` of length `i` from the beginning of `s` (i.e., `s[:i]` in Python, `s.substring(0, i)` in Java/C++).
Step 5: Create a new string `repeated` by repeating the substring `sub` `n // i` times. For example, in python this can be done by `substring * (n // i)`.
Step 6: Compare the `repeated` string with the original string `s`. If they are equal, return `true` because `s` can be formed by repeating `sub`.
Step 7: If the loop finishes without finding any repeating substring, return `false`.

Key Insights

Insight 1: If a string `s` is formed by repeating a substring, then the length of the substring must be a divisor of the length of `s`. This is because the substring must fit an integer number of times within `s`.
Insight 2: We can iterate through all possible substring lengths that are divisors of the string's length. For each possible length, we extract the substring and check if repeating it generates the original string.
Insight 3: The search space for the length of substring can be reduced to be less than or equal to half of the length of original string, since the substring must be repeated at least twice to form the string.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n)

Topics

This problem involves: String, String Matching.

Companies

Asked at: Myntra.

Repeated Substring Pattern | LeetCode 459

Easy

String String Matching

Time: O(n^2)Space: O(n)

Solution Code

Available in:

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);
                boolean match = true;
                for (int j = i; j < n; j += i) {
                    if (!s.substring(j, Math.min(j + i, n)).equals(sub)) {
                        match = false;
                        break;
                    }
                }
                if (match) return true;
            }
        }
        return false;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 459: Repeated Substring Pattern - Detailed explanation and solution approaches.

Topics

String String Matching

Companies

Myntra

Stats

Difficulty:Easy

Languages:4

Companies:1

Problem #:459

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Get the length `n` of the input string `s`.
2
Step 2: Iterate from `i = 1` to `n // 2` (inclusive). This loop represents the possible lengths of the repeating substring.
3
Step 3: Inside the loop, check if `n` is divisible by `i` (i.e., `n % i == 0`). If it is, it means `i` could be the length of the repeating substring.
4
Step 4: If `n % i == 0`, extract the substring `sub` of length `i` from the beginning of `s` (i.e., `s[:i]` in Python, `s.substring(0, i)` in Java/C++).
5
Step 5: Create a new string `repeated` by repeating the substring `sub` `n // i` times. For example, in python this can be done by `substring * (n // i)`.
6
Step 6: Compare the `repeated` string with the original string `s`. If they are equal, return `true` because `s` can be formed by repeating `sub`.
7
Step 7: If the loop finishes without finding any repeating substring, return `false`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The outer loop iterates up to `n/2` times (O(n)). Inside the loop, the string concatenation `substring * (n // i)` (in python) creates a new string of length `n`, taking O(n) time. Similarly, the string comparison `repeated == s` also takes O(n) time. Therefore, the overall time complexity is O(n * n) = O(n^2). The string construction takes O(n) space, and the substring variable is bounded by O(n), so the space complexity is O(n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

KMP Algorithm

Use the Knuth-Morris-Pratt (KMP) algorithm for string matching. Construct the LPS (Longest Proper Prefix which is also a Suffix) array for the input string `s`. If `s` can be formed by repeating a substring, then `len(s) % (len(s) - lps[-1]) == 0`, where `lps` is the LPS array.

Time: O(n)Space: O(n)

Trade-offs: KMP offers better time complexity (O(n) vs O(n^2)) but requires understanding and implementation of the KMP algorithm. It is more complex to implement than the naive approach. Use KMP if performance is critical and the string length is very large.

String Concatenation and Search

Concatenate the string with itself (s + s) and remove the first and last characters. If the original string `s` is a substring of this new string, then `s` is formed by repeating a substring.

Time: O(n)Space: O(n)

Trade-offs: This method is efficient in terms of time complexity, and has a simple implementation. It is beneficial for scenarios where memory usage is not a major constraint.

✨

Key Insights

1Insight 1: If a string `s` is formed by repeating a substring, then the length of the substring must be a divisor of the length of `s`. This is because the substring must fit an integer number of times within `s`.
2Insight 2: We can iterate through all possible substring lengths that are divisors of the string's length. For each possible length, we extract the substring and check if repeating it generates the original string.
3Insight 3: The search space for the length of substring can be reduced to be less than or equal to half of the length of original string, since the substring must be repeated at least twice to form the string.

📚

Key Terms Explained

For Students

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string. The problem statement specifies 1 <= s.length, so an empty string is not an input. Therefore, no special handling is needed.
Edge case 2: String of length 1. For example, 'a'. The loop will not execute (range(1, 0 + 1) is an empty range), and the function will correctly return `false`.
Edge case 3: Prime length string. If the string's length is a prime number, the only divisors are 1 and itself. The loop only goes up to n//2, and if no match is found, it returns false. Consider 'abcde', it returns false. This is the correct behaviour.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not checking if the substring length is a divisor of the original string's length. This will lead to incorrect results.

✗Common mistake 2: Incorrectly implementing the substring repetition or comparison. Ensure the correct substring is extracted and repeated the appropriate number of times.

✗Common mistake 3: Looping through the entire string length instead of only up to half the string length. Substrings repeated more than once will always be of at most length(s)/2

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data compression. Identifying repeating patterns in data can be used to compress the data efficiently.

🏦Real-world scenario 2: Bioinformatics. Finding repeating sequences in DNA or protein sequences can reveal important biological information about genes and proteins.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 30

❓

Frequently Asked Questions

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Repeated Substring Pattern"?

For this easy-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string matching techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?