LeetCode 2796 - Repeat String

LeetCode Problem 2796

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

This problem asks us to extend the behavior of strings so that every string supports a replicate(x) method. The method should return a new string where the original string is repeated exactly x times.

For example, if the string is "hello" and x = 2, the result should be "hellohello". If the string is "code" and x = 3, the result becomes "codecodecode".

The important restriction is that we are not allowed to use the built in string.repeat() method. That means we must manually construct the repeated string ourselves.

The follow up introduces an interesting theoretical optimization. Normally, repeating a string n times using a loop requires O(n) concatenation operations. However, if we assume that string concatenation itself costs O(1), then we can improve the algorithm to O(log n) using a doubling technique similar to binary exponentiation.

The input consists of:

• A string str
• An integer times

The output is a new string formed by concatenating the original string exactly times times.

The constraints are:

• 1 <= times <= 10^5
• 1 <= str.length <= 1000

These constraints tell us that the output itself can become very large. For example, a string of length 1000 repeated 100000 times produces a result with length 100,000,000. Because the output size dominates the runtime in practice, any real implementation must at least spend time proportional to the output size.

Several edge cases are important:

• Repeating a string exactly once should return the original string unchanged.
• Very large repetition counts can expose inefficient concatenation approaches.
• Empty repetition counts are not possible because the constraints guarantee times >= 1.
• Strings containing special characters or spaces should still concatenate correctly.

Approaches

Brute Force Approach

The most direct solution is to repeatedly append the string to a result variable exactly times times.

We begin with an empty string. Then, for each iteration, we concatenate the original string onto the result.

For example:

• Start with result = ""
• Add "abc" → "abc"
• Add "abc" again → "abcabc"
• Continue until the string has been added times times

This approach is simple and obviously correct because each iteration contributes exactly one copy of the original string.

However, this method performs one concatenation per repetition. Under standard string cost assumptions, repeated concatenation can become inefficient because each new concatenation may copy the existing contents.

Optimal Approach

The key observation is that we can build repeated strings using a doubling strategy, similar to fast exponentiation.

Instead of appending the original string one time per iteration, we repeatedly double a temporary string:

• "a"
• "aa"
• "aaaa"
• "aaaaaaaa"

At each step, we inspect the binary representation of times.

If the current bit is set, we append the current doubled block to the answer.

This reduces the number of concatenation operations from O(n) to O(log n) under the simplified assumption that concatenation costs O(1).

The idea is exactly the same as exponentiation by squaring:

• Repeated addition becomes multiplication
• Repeated concatenation becomes repeated doubling

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Appends the string once per repetition
Optimal	O(log n) under constant time concatenation assumption	O(n)	Uses binary decomposition and doubling

Algorithm Walkthrough

Optimal Binary Doubling Algorithm

1. Initialize an empty result string.

This string will eventually contain the final repeated output. 2. Store the original string in a temporary variable called current.

This variable represents the current doubled block of strings. 3. While times is greater than zero, examine its least significant bit.

If the current bit is 1, append current to the result. This means the current power of two contributes to the final answer. 4. Double the current string by concatenating it with itself.

For example:

• "ab" becomes "abab"
• "abab" becomes "abababab"

Each doubling represents the next power of two. 5. Divide times by two using integer division.

This shifts us to the next binary bit. 6. Continue until all bits of times have been processed. 7. Return the final result string.

Why it works

The algorithm works because every integer can be represented as a sum of powers of two.

For example:

• 13 = 8 + 4 + 1
• Binary representation: 1101

We generate repeated string blocks corresponding to powers of two:

• 1 copy
• 2 copies
• 4 copies
• 8 copies

Whenever a binary bit is set, we include that block in the result. Therefore, the final concatenation contains exactly the required number of repetitions.

Python Solution

class Solution:
    def replicate(self, string: str, times: int) -> str:
        result = ""
        current = string

        while times > 0:
            if times & 1:
                result += current

            current += current
            times >>= 1

        return result

The implementation starts by initializing two strings:

• result, which stores the final answer
• current, which stores the current doubled block

The loop processes the binary representation of times.

The condition times & 1 checks whether the current least significant bit is set. If it is, the current block contributes to the final result.

Afterward, current += current doubles the size of the current repeated block.

Finally, times >>= 1 shifts the integer one bit to the right, moving to the next binary digit.

The loop terminates once all bits have been processed.

Go Solution

package main

type Solution struct{}

func (s Solution) Replicate(str string, times int) string {
	result := ""
	current := str

	for times > 0 {
		if times&1 == 1 {
			result += current
		}

		current += current
		times >>= 1
	}

	return result
}

The Go implementation follows exactly the same logic as the Python version.

One difference is that Go uses explicit type declarations and method receivers. The bitwise operations work identically.

Strings in Go are immutable just like Python strings, so concatenation creates new strings internally. Under realistic complexity assumptions, the runtime is still proportional to the final output size.

Worked Examples

Example 1

Input:

str = "hello"
times = 2

Binary representation of 2 is 10.

Step	times	Binary	current	result
Initial	2	10	hello	""
Bit not set	2	10	hellohello	""
Bit set	1	1	hellohello	hellohello
End	0	0	doubled again	hellohello

Final result:

"hellohello"

Example 2

Input:

str = "code"
times = 3

Binary representation of 3 is 11.

Step	times	Binary	current	result
Initial	3	11	code	""
Bit set	3	11	codecode	code
Bit set	1	1	codecodecodecode	codecodecode
End	0	0	doubled again	codecodecode

Final result:

"codecodecode"

Example 3

Input:

str = "js"
times = 1

Step	times	current	result
Initial	1	js	""
Bit set	1	jsjs	js
End	0	jsjs	js

Final result:

"js"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n) under idealized assumptions	Each iteration processes one binary bit
Space	O(n)	The output string itself requires linear space

Under realistic string models, the runtime must also account for the size of the generated output. Since the output contains times * len(str) characters, practical runtime is at least proportional to the final string length.

The follow up complexity only applies under the artificial assumption that concatenation costs O(1).

Test Cases

solution = Solution()

assert solution.replicate("hello", 2) == "hellohello"  # basic repetition
assert solution.replicate("code", 3) == "codecodecode"  # multiple repetitions
assert solution.replicate("js", 1) == "js"  # single repetition
assert solution.replicate("a", 5) == "aaaaa"  # single character
assert solution.replicate("ab", 4) == "abababab"  # even repetition count
assert solution.replicate("xyz", 7) == "xyzxyzxyzxyzxyzxyzxyz"  # odd repetition count
assert solution.replicate(" ", 3) == "   "  # whitespace handling
assert solution.replicate("!@", 2) == "!@!@"  # special characters
assert len(solution.replicate("x", 100000)) == 100000  # stress test

Test Summary

Test	Why
"hello", 2	Verifies normal repetition
"code", 3	Verifies odd repetition counts
"js", 1	Verifies minimum repetition count
"a", 5	Verifies single character strings
"ab", 4	Verifies repeated doubling behavior
"xyz", 7	Verifies binary decomposition logic
" ", 3	Verifies whitespace handling
"!@", 2	Verifies special character support
"x", 100000	Verifies scalability

Edge Cases

Repeating Exactly Once

A common bug is accidentally modifying the string when times = 1.

For example:

"js" -> "js"

The algorithm handles this naturally because the first binary bit is set, so the original string is appended exactly once before the loop terminates.

Large Repetition Counts

Very large values of times can expose inefficient implementations that repeatedly concatenate small pieces.

For example:

str = "x"
times = 100000

The doubling approach reduces the number of concatenation operations from linear in times to logarithmic in times, under the follow up assumptions.

Special Characters and Spaces

Some implementations incorrectly assume inputs contain only letters.

Examples such as:

" "
"!@"

must still behave correctly.

Since the algorithm treats strings as generic sequences of characters, all characters are concatenated identically without special handling.