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 determine whether the given string s can be a result of repeating a substring.

Clarifying Questions

  1. Input Constraints:
    • What is the length of string s? (Typical interview ensures we handle up to (10^5) characters)
    • Are there any specific characters allowed, or any character in ASCII range?
  2. Output:
    • Should return a boolean value: true if the string can be constructed by repeating a substring, otherwise false.

Strategy

  1. Concatenation Method: If the original string s can be constructed by repeating a substring, then repeating this string minus its first and last character should contain s exactly once. This involves:
    • Creating a new string t by concatenating s with itself (e.g., if s = "abcabc", then t = "abcabcabcabc")
    • Removing the first and the last character from t (e.g., t = "bcabcabcabcab")
    • Checking if s exists in this adjusted t.
  2. Prefix-Suffix Array (KMP Algorithm): Using the prefix-suffix table (LPS array from KMP algorithm) to determine the longest pattern which is both a proper prefix and suffix. If such a pattern exists and divides the length of the string perfectly, s can be constructed by repeating that substring.

For brevity, we will implement the first method as it is simpler to code and understand.

Code

#include <iostream>
#include <string>

bool repeatedSubstringPattern(const std::string& s) {
    if (s.empty()) return false;

    std::string t = s + s;
    std::string truncated = t.substr(1, t.size() - 2);

    return truncated.find(s) != std::string::npos;
}

int main() {
    std::string test1 = "abab";
    std::string test2 = "aba";
    std::string test3 = "abcabcabcabc";

    std::cout << std::boolalpha;  // to print `true/false` instead of 1/0
    std::cout << repeatedSubstringPattern(test1) << std::endl;  // Should print true
    std::cout << repeatedSubstringPattern(test2) << std::endl;  // Should print false
    std::cout << repeatedSubstringPattern(test3) << std::endl;  // Should print true

    return 0;
}

Time Complexity

The time complexity of this solution is dominated by the find operation, which typically runs in (O(N)) in average cases, where (N) is the length of string s. Therefore:

This method leverages string manipulation and searching in an efficient manner to determine if the string can be constructed through repetition without complex preprocessing.

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