algoadvance

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 if s can be constructed using any substring with more than one character.

Clarifying Questions

1. What is the length range for the input string s?
   • The input string length ranges from 1 to 10^4.
2. Can the input string s contain any characters other than lowercase English letters?
   • No, s consists only of lowercase English letters.
3. Should we consider edge cases such as the input string being of length 1?
   • Yes, we should consider such cases. A single character string cannot form a repeated substring pattern.

Strategy

1. Observation: If a string s can be formed by repeating a substring p, then concatenating s with itself (i.e., s + s) and removing the first and last characters must contain the original string s in some position other than the start.

2. Steps:
   • Create a new string ss by concatenating s with itself.
   • Remove the first and last characters from ss.
   • Check if the original string s exists in the modified ss.
   • If s exists in the modified ss, then s can be constructed by repeating a substring.
3. Return:
   • Return True if s is found in modified ss.
   • Otherwise, return False.

Time Complexity

• The time complexity of creating ss and modifying it is O(n), where n is the length of the input string s.
• The time complexity for checking if s is a substring of the modified ss is also O(n) using Python’s in operator.
• Overall, the time complexity of the solution is O(n), which is efficient given the problem constraints.

Code

def repeatedSubstringPattern(s: str) -> bool:
    # Concatenate the string with itself
    ss = (s + s)[1:-1]
    # Check if the original string s is inside the modified ss
    return s in ss

# Example Usage
print(repeatedSubstringPattern("abab"))  # Output: True
print(repeatedSubstringPattern("aba"))   # Output: False
print(repeatedSubstringPattern("abcabcabc")) # Output: True
print(repeatedSubstringPattern("abcab")) # Output: False

The above code provides a straightforward and efficient method to determine if a string can be constructed by repeating a substring, leveraging string manipulation and pattern recognition techniques.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?