We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Repeat String

Number: 2899

Difficulty: Easy

Paid? Yes

Companies: N/A

Problem Description

Enhance all strings such that a new method replicate(x) can be called on any string, returning the string repeated x times. You cannot use the built-in repeat method. Additionally, assume that string concatenation is O(1) and aim for an algorithm with runtime complexity O(log n).

Key Insights

  • Use an algorithm that employs doubling (binary exponentiation-style) to achieve O(log n) time complexity.
  • On each iteration, if the current power bit is set (i.e. times is odd), concatenate the current portion to the result.
  • Double the string (i.e. current = current + current) and halve the number of repetitions.
  • This approach minimizes the number of concatenations required.

Space and Time Complexity

Time Complexity: O(log n) — because we reduce the number of iterations by half on each step. Space Complexity: O(m * n) in worst case where m is the length of the string and n is the number of times (assuming the concatenated result occupies that much space).

Solution

The solution uses a doubling strategy similar to fast exponentiation. We maintain two variables: one for the final result and one for the current string segment. As we loop while times > 0, we check if the current repetition count is odd. If yes, we append the current segment to the result. Then we double the current segment (i.e., replicate it by itself) and halve the count. This efficiently builds the final repeated string in O(log times) iterations under the given assumption that concatenation operates in constant time.

Code Solutions

# Enhance the string by defining a function replicate on the string type
def replicate(input_str, times):
    # Initialize the result string as empty
    result = ""
    # The current string segment starts as the input string
    current_segment = input_str
    # Loop until times is zero
    while times > 0:
        # If the current counter is odd, add current_segment to result
        if times % 2 == 1:
            result += current_segment  # Append the segment if the bit is set
        # Double the current segment
        current_segment += current_segment
        # Halve the times (integer division)
        times //= 2
    # Return the final repeated string
    return result

# Example usage:
print(replicate("hello", 2))  # Expected output: "hellohello"
print(replicate("code", 3))   # Expected output: "codecodecode"
print(replicate("js", 1))     # Expected output: "js"
← Back to All Questions