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?

Solution 1

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.

Solution 2

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.

Solution 3

StringBuilder would improve the memory footprint here:

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

Solution 4

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())

Solution 5

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

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

View more solutions

Comments

[Rainmaker]

Looks good, thanks! Seems like there is no way to do it faster then O(n), what do you think?

[zsmb13]

If you look at the same question for Java (here or here for example) everything seems to involve looping through the length of the string / array once.

[marstran]

@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.