algoadvance

Leetcode 459. Repeated Substring Pattern

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. You need to return true if s can be constructed from a substring, otherwise return false.

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.

Clarifying Questions

  1. What is the length of the input string?
    • The length of the string s will be between 1 and 10^4.
  2. What characters are allowed in the input string?
    • The input string s consists of lowercase English letters only.
  3. Should the solution be case-sensitive?
    • As the input contains only lowercase English letters, case-sensitivity is not an issue.
  4. Are there any constraints on memory usage?
    • No specific constraints, but the solution should be efficient given the potential length of the input.

Strategy

The problem can be solved by utilizing a string manipulation trick:

  1. Double the string: If s is composed of repeating a substring, doubling s and then removing the first and the last character will still contain s somewhere in the middle.
  2. Search for the original string in this modified string: If the modified string contains the original string, then the original string is a repeating substring pattern.

Code

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String doubled = s + s;
        String modified = doubled.substring(1, doubled.length() - 1);
        return modified.contains(s);
    }
}

Time Complexity

Detailed Explanation

  1. Double the string:
    • Concatenate s with itself to get doubled = s + s.
  2. Modify the doubled string:
    • Remove the first and the last character from doubled to form modified.
  3. Check for the pattern:
    • If s is present in modified, then s can be formed by repeating some substring. Hence, return true.
    • Otherwise, return false.

This approach leverages string manipulation to efficiently determine if a string has a repeated substring pattern.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI