repeat string n times in Kotlin

Question

I want to create a string which would contain a * symbol n times. I only see this way:

val s = ""
val n = 100
for (j in 0 until n) {
    s += "*"
}

But it looks ugly and it has a O(n^2) time complexity. Is there a way in Kotlin to do that without a loop with better time complexity?

This is actually O(n²) because `s += "*"` recreates the whole string (length 1 to n) with one more "*" added. — DodgyCodeException, Jan 25 '18 at 15:26
To solve the performance problem use `val s = StringBuilder(n)` — voddan, Jan 26 '18 at 10:11

score 81 · Accepted Answer · answered Jan 25 '18 at 15:27

81

The built in CharSequence.repeat extension does this in an efficient way, see the source here.

val str: String = "*".repeat(100)

Of course, this will still require O(n) steps to create the string. However, using this built-in stdlib function has its advantages: it's cross-platform, easy to read, and can be improved in performance over time, if there's a more efficient solution. The loop inside it will probably be optimized by the compiler or the runtime anyway.

answered Jan 25 '18 at 15:27

zsmb13

85,752
11
221
226

Looks good, thanks! Seems like there is no way to do it faster then O(n), what do you think? – Rainmaker Jan 25 '18 at 15:40
If you look at the same question for Java ([here](https://stackoverflow.com/q/2804827/4465208) or [here](https://stackoverflow.com/q/16800295/4465208) for example) everything seems to involve looping through the length of the string / array once. – zsmb13 Jan 25 '18 at 15:55
2

@Rainmaker There is no way to add n strings together in less than O(n). You will always need to visit each string at least once. – marstran Jan 25 '18 at 16:10

Martin · Answer 2 · 2019-04-17T15:43:11.980

6

You can overload the * operator to map it to the existing repeat extension:

public operator fun CharSequence.times(count: Int): String {
    return repeat(count)
}

fun main() {
    val s = "*" * 101
    println(s)
    println("Badger " * 12 + "Mushroom " * 2)
    println(s)
}

edited Apr 17 '19 at 15:43

answered Apr 17 '19 at 15:11

Martin

2,573
28
22

score 4 · Answer 3 · answered Jan 25 '18 at 22:50

4

An alternative to the CharSequence.repeat is a CharArray with an init function:

CharArray(N, {i -> '*'}).joinToString(separator="")

This solution has the advantage that you can define prefix, postfix, and separator.

answered Jan 25 '18 at 22:50

Christian Kuka

111
3

Kotlin 1.4 introduced [`CharArray.concatToString()`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.text/concat-to-string.html), so if you don't need the extras from `joinToString()` you can also do `CharArray(10) { '*' }.concatToString()` – aSemy Aug 18 '22 at 12:11

score 3 · Answer 4 · answered Jan 25 '18 at 15:26

3

StringBuilder would improve the memory footprint here:

val sb = StringBuilder() 
val n = 100
for (j in 0 until n) {
  sb.append("*") 
}

answered Jan 25 '18 at 15:26

Anton Sizikov

9,105
1
28
39

Yes, it's better, thanks, but it's still loop and still O(n) – Rainmaker Jan 25 '18 at 15:27
1

O(n) is better than the original O(n^2), tho – Anton Sizikov Jan 25 '18 at 15:28
Why n^2? There is only one loop – Rainmaker Jan 25 '18 at 15:29
2

strings are immutable, hence the n^2 to copy the result on each concatenation. – Anton Sizikov Jan 25 '18 at 15:31
3

You don't have to instantiate the StringBuilder, do it like this instead: val result = buildString { (0..100).forEach { append("*") } } – Jan 25 '18 at 15:38
@Rainmaker you can't beat O(n) for repeating a string `n` times, but the point about the loop is true. Still, this is a welcome addition to the accepted answer as a generalization. – ggorlen Oct 26 '21 at 05:20

score 3 · Answer 5 · answered Jul 23 '20 at 12:04

3

If you need a separator, this initializer function from List is helpful:

val str: String = List(100) { "*" }.joinToString(",")

answered Jul 23 '20 at 12:04

MrMox

191
2
4

CoolMind · Answer 6 · 2019-04-09T07:33:38.410

Thanks to Anton Sizikov and https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/repeat.html, we can write:

val sb = StringBuilder().apply{
    repeat(100) {
        append("*")
    }
}

But this is a simple way. Look at a power function. It has O(log n) complexity.

For StringBuilder:

private fun power(sb: StringBuilder, n: Int): StringBuilder =
    when {
        n == 0 -> StringBuilder("")
        n % 2 == 0 -> {
            val part = power(sb, n / 2)
            part.append(part)
        }
        else -> {
            val part = power(sb, n / 2)
            part.append(part).append(sb)
        }
    }

For String:

private fun pow(s: String, n: Int): String =
    when {
        n == 0 -> ""
        n % 2 == 0 -> pow(s, n / 2).repeat(2)
        else -> s + pow(s, n / 2).repeat(2)
    }

Then we can invoke them:

// 1.
val sb1 = StringBuilder().apply {
    repeat(100) {
        append("*")
    }
}

// 2.
val sb2 = power(StringBuilder("*"), 100)

// 3.
val s = power("*", 100)

println(sb1.toString())
println(s)
println(sb2.toString())

repeat string n times in Kotlin

6 Answers6