Repeat String solution and explanation
The problem
Write code that enhances all strings such that you can call the string.replicate(x) method on any string and it will return repeated string x times.
Try to implement it without using the built-in method string.repeat.
Example 1:
Input: str = "hello", times = 2 Output: "hellohello" Explanation: "hello" is repeated 2 times
Example 2:
Input: str = "code", times = 3 Output: "codecodecode" Explanation: "code" is repeated 3 times
Example 3:
Input: str = "js", times = 1 Output: "js" Explanation: "js" is repeated 1 time
Constraints:
1 <= times <= 1051 <= str.length <= 1000
O(1). With this assumption in mind, can you write an algorithm with a runtime complexity of O(log n)?Approach overview
Problem Overview: You are given a base string s and an integer k. The task is to construct a new string formed by repeating s exactly k times. For example, if s = "ab" and k = 3, the result should be "ababab".
Approach 1: Iterative Concatenation (O(n * k) time, O(n * k) space)
The straightforward way is to build the result string step by step. Start with an empty string and iterate k times. During each iteration, append the original string s to the result. Each append copies characters from s, so if s has length n, the total work becomes n * k. The final string also stores n * k characters, which leads to O(n * k) space usage. This method uses basic string manipulation and a simple loop, making it easy to implement and understand.
Approach 2: Built-in Repeat Method (O(n * k) time, O(n * k) space)
Most languages provide a built-in utility to repeat a string multiple times. In JavaScript and TypeScript, the String.prototype.repeat() method handles this directly. Calling s.repeat(k) internally allocates a new string and copies the characters of s k times. The algorithmic complexity remains O(n * k) because every character still needs to be written to the final output. The benefit is cleaner code and fewer chances for off-by-one mistakes. This approach relies purely on string operations and avoids manual loops.
Although the logic is simple, understanding the cost of string construction is useful. Each repetition requires copying characters into the result buffer. Languages with immutable strings allocate new memory for the final result, so the total memory footprint grows linearly with the output length.
Recommended for interviews: The iterative approach demonstrates that you understand how string construction works internally. However, interviewers typically expect you to use the built-in repeat() function when available because it expresses intent clearly and keeps the implementation concise. Both approaches rely on fundamental string manipulation concepts and run in linear time relative to the size of the produced string.
Solution
String.prototype.replicate = function (times) {
return Array(times).fill(this).join('');
};declare global {
interface String {
replicate(times: number): string;
}
}
String.prototype.replicate = function (times: number) {
return new Array(times).fill(this).join('');
};Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Concatenation | O(n * k) | O(n * k) | When implementing manually or when built-in repeat utilities are unavailable |
| Built-in repeat() Method | O(n * k) | O(n * k) | Preferred in JavaScript/TypeScript for concise and readable implementation |
Frequently asked questions
Is Repeat String easy or hard?
Repeat String is considered an easy problem. The logic relies on simple loops or built-in string utilities, and the main concept is understanding how repeated concatenation builds the final string.
Repeat String Python/Java solution
In Python, the expression s * k repeats the string k times. In Java, you can use s.repeat(k) starting from Java 11 or build the result with a loop and StringBuilder. Both approaches run in O(n * k) time.
How to solve Repeat String in O(n)?
The effective complexity depends on the final output length. If the resulting string length is n * k, any correct solution must process that many characters. Using a built-in repeat function achieves optimal linear work relative to the produced string size.
What is the best approach for Repeat String?
The best approach is using the built-in string repeat function such as JavaScript's String.prototype.repeat(). It constructs the result in O(n * k) time where n is the length of the string and k is the number of repetitions. The method is concise and avoids manual loops.
Is Repeat String asked at Google/Amazon/Meta?
Repeat String is a basic string manipulation problem commonly used in coding assessments and early interview rounds. While top companies often ask more complex variations, this type of problem checks understanding of loops and string operations.
What data structure is used in Repeat String?
The solution primarily uses string operations. Internally, implementations allocate a new character buffer to store the repeated result while iterating or copying characters from the original string.
What is the time complexity of Repeat String?
The time complexity is O(n * k). Every character of the original string of length n must be copied k times to form the final string, so the total number of operations scales with the output size.