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.

Examples

Example 1:

1
2
3

Input: str = "hello", times = 2
Output: "hellohello"
Explanation: "hello" is repeated 2 times

Example 2:

1
2
3

Input: str = "code", times = 3
Output: "codecodecode"
Explanation: "code" is repeated 3 times

Example 3:

1
2
3

Input: str = "js", times = 1
Output: "js"
Explanation: "js" is repeated 1 time

Constraints:

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

Follow up: Let’s assume, for the sake of simplifying analysis, that concatenating strings is a constant time operation O(1). With this assumption in mind, can you write an algorithm with a runtime complexity of O(log n)?

Solution

Method 1 - Prototype Extension (O(n) and O(log n) approaches)

Intuition

We want to add a method to all strings that returns the string repeated x times, without using the built-in repeat. The naive way is to concatenate in a loop (O(n)), but we can do better with exponentiation by squaring (O(log n)).

Approach

O(n) approach:

  1. Add a method to String.prototype called replicate.
  2. Use a loop to concatenate the string x times.

O(log n) approach (Follow up):

  1. Use exponentiation by squaring: double the string and halve the count at each step, appending to result when needed.

Code

1
2
3
4
5
6
7

String.prototype.replicate = function(times) {
    let res = '';
    for (let i = 0; i < times; i++) {
        res += this;
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

String.prototype.replicate = function(times) {
    let res = '';
    let base = this.valueOf();
    while (times > 0) {
        if (times % 2 === 1) res += base;
        base += base;
        times = Math.floor(times / 2);
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

declare global {
    interface String {
        replicate(times: number): string;
    }
}
String.prototype.replicate = function(times: number): string {
    let res = '';
    let base = this.valueOf();
    while (times > 0) {
        if (times % 2 === 1) res += base;
        base += base;
        times = Math.floor(times / 2);
    }
    return res;
}
export {};

Complexity

  • ⏰ Time complexity: O(n) for the naive approach, O(log n) for the exponentiation by squaring approach (assuming O(1) string concat).
  • 🧺 Space complexity: O(n * m), where n = times, m = str.length (for the result string).