41

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?

3
  • This is actually O(n²) because s += "*" recreates the whole string (length 1 to n) with one more "*" added. Commented Jan 25, 2018 at 15:26
  • I corrected the question, thanks
    – Rainmaker
    Commented Jan 25, 2018 at 15:31
  • 1
    To solve the performance problem use val s = StringBuilder(n)
    – voddan
    Commented Jan 26, 2018 at 10:11

6 Answers 6

93

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.

3
  • Looks good, thanks! Seems like there is no way to do it faster then O(n), what do you think?
    – Rainmaker
    Commented Jan 25, 2018 at 15:40
  • 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.
    – zsmb13
    Commented Jan 25, 2018 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
    Commented Jan 25, 2018 at 16:10
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)
}
5

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.

1
  • Kotlin 1.4 introduced CharArray.concatToString(), so if you don't need the extras from joinToString() you can also do CharArray(10) { '*' }.concatToString()
    – aSemy
    Commented Aug 18, 2022 at 12:11
5

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

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

StringBuilder would improve the memory footprint here:

val sb = StringBuilder() 
val n = 100
for (j in 0 until n) {
  sb.append("*") 
}
7
  • Yes, it's better, thanks, but it's still loop and still O(n)
    – Rainmaker
    Commented Jan 25, 2018 at 15:27
  • 1
    O(n) is better than the original O(n^2), tho Commented Jan 25, 2018 at 15:28
  • Why n^2? There is only one loop
    – Rainmaker
    Commented Jan 25, 2018 at 15:29
  • 2
    strings are immutable, hence the n^2 to copy the result on each concatenation. Commented Jan 25, 2018 at 15:31
  • 3
    You don't have to instantiate the StringBuilder, do it like this instead: val result = buildString { (0..100).forEach { append("*") } }
    – anon
    Commented Jan 25, 2018 at 15:38
1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.