Idiomatic Kotlin: Merge Two Strings Alternately + Benchmarks

Big Brain Kotlin Time — Merging Two Strings alternately

Feature on Kotlin Weekly #377

Kotlin Weekly #377

Try it yourself: https://leetcode.com/problems/merge-strings-alternately

Hi Guys, It has been a while since I wrote an article and there have been a lot of changes going through Android and Kotlin Community from Compose to Kotlin Multiplatform, all things are exciting and fun but due to major changes in my life going on too I am not getting enough time to write some major articles on them, so I decided to get on habit of writing by writing small.

As from the title, you might have figured out we are solving a problem which is Merging Two String Alternately in Kotlin-ish way! if you have missed out on my series that was helping devs to write better code with Kotlin do check out this link: https://chetangupta.net/bbk-main/

Disclaimer I am here you helped write clean Kotlin not optimised one, but be sure I will not try to make you a janky developer, anyways I'm always open to feedback like here I am helping out by sharing my experience do share yours as well for mutual benefit and leaning so chrees and enjoy rest of read!

Solution #1 🤖

if our inputs are abc and xyz we would get output axbycz but if its ab and xyz we will get output axbyz

Let's a normal approach

fun mergeAlternately(word1: String, word2: String): String {

    // Initialize indexes to track position in each string
    var trackWord1 = 0
    var trackWord2 = 0

    // StringBuilder to efficiently build result
    val stringBuilder = StringBuilder()

    // Loop while both strings have characters left
    while (trackWord1 < word1.length && trackWord2 < word2.length) {

        // Append next character from first string
        stringBuilder.append(word1[trackWord1])

        // Increment index to next character
        trackWord1++

        // Append next character from second string
        stringBuilder.append(word2[trackWord2])

        // Increment index to next character
        trackWord2++
    }

    // Append remaining characters from longer string
    for (index in trackWord1 until word1.length) {
        stringBuilder.append(word1[index])
    }

    for (index in trackWord2 until word2.length) {
        stringBuilder.append(word2[index])
    }

    // Return final merged string
    return stringBuilder.toString()
}

TLDR

1. Use indexes to iterate through both strings
2. Loop appending chars alternately while both have chars left
3. Append remaining chars from longer string
4. StringBuilder efficiently builds result string
5. Return a final merged string

Pros:

1. Simple and easy-to-understand logic
2. Iterates strings sequentially with indexes
3. Appends characters efficiently with StringBuilder
4. Handles strings of different lengths gracefully
5. Do not use extra space beyond the result string

Cons:

1. We can remove longer string append logic with different loop
2. We can improve StringBuilder
3. We can introduce scoped mutations

Solution #2 : Let’s be Kotlini 🧩

fun mergeAlternately(word1: String, word2: String): String {

    // Build result string with initial capacity
    // of both string lengths combined
    return buildString(word1.length + word2.length) {

        // Repeat max of two string lengths
        repeat(kotlin.math.max(word1.length, word2.length)) { iteration ->

            // If index is valid for first string
            // append character at that index
            if (iteration < word1.length) append(word1[iteration])

            // If index is valid for second string
            // append character at that index
            if (iteration < word2.length) append(word2[iteration])
        }
    }
}

TLDR

1. buildString() avoids intermediate StringBuilder
2. Initial capacity reduces internal array resizes
3. Repeat max length to cover both strings
4. Append char if index is valid using if checks
5. Returns final merged string

Pros:

1. Concise syntax compared to explicit StringBuilder
2. Initial capacity minimizes internal array resizes
3. Repeats loop instead of manual indices
4. Single append call per character
5. Handles strings of different lengths
6. Keeps merging logic contained and scoped
7. Easiest to maintain

Cons:

1. Max length repeat does extra iterations

Bonus 🔗

I always share a standard library function that could perform the same functionality but unfortunately, we don't have equally same this time.

What comes close to it is zip operation in Kotlin can group two iterators together.

val string1 = "abc"
val string2 = "xyz"
val zipped = string1.zip(string2)

println(zipped)//output: [(a, x), (b, y), (c, z)]

but where it fails is when strings are of not equal length

val string1 = "ab" // unequal string sizes
val string2 = "xyz"
val zipped = string1.zip(string2)

println(zipped)//output: [(a, x), (b, y)]

can we overcome this??? Well Yes check the following snippet, but I will recommend to ignore this approach :

fun mergeAlternatelyWithZip(word1: String, word2: String): String {
    // Determine the shorter and longer strings
    val minString = if (word1.length > word2.length) word2 else word1
    val maxString = if (word1.length > word2.length) word1 else word2

    // Zip the characters from the shorter and longer strings, and join them into a single string
    val zipped = minString.zip(maxString).joinToString("") { "${it.first}${it.second}" }

    // Get the remaining characters from the longer string
    val remaining = maxString.slice(minString.length until maxString.length)

    // Append the remaining characters from the longer string, if any
    return zipped + remaining
}

• Why substring over slice? https://chetangupta.net/bbk7/
• Mastering List to String? https://chetangupta.net/list-to-string/

Benchmark Time 🕗

I used the KotlinX benchmark library to Benchmark these functions on the Kotlin JVM project with 5 warmups and 20 iterations configuration and the results were :

Main Summary:

Benchmark                                                   Mode  Cnt         Score         Error  Units
MergeAlternativeBenchmark.mergeAlternatelyWithBuildString  thrpt   20  48881974.955 ± 1085747.284  ops/s
MergeAlternativeBenchmark.mergeAlternatelyWithWileLoop     thrpt   20  34447752.568 ±  788824.669  ops/s
MergeAlternativeBenchmark.mergeAlternatelyWithZip          thrpt   20  16864008.578 ±  426691.695  ops/s

higher the score better the performance.

Here’s a breakdown of the report:

1. Benchmark: This column displays the name of the benchmark method being tested.
2. Mode: The mode used for benchmarking, which in this case is “thrpt” (throughput). In throughput mode it measures how many operations can be executed per unit of time.
3. Cnt: The number of benchmark iterations performed during the benchmark run. In your example, each benchmark was executed 5 times.
4. Score: The primary metric of interest. It represents the throughput of the benchmark method in operations per second (ops/s). A higher score indicates better performance.
5. Error: The error associated with the score. This value represents the variability or uncertainty in the measurement. A smaller error is preferable, indicating a more stable measurement.
6. Units: The units in which the score is expressed, typically “ops/s” for throughput measurements.

In our report, the final scores are :

mergeAlternatelyWithBuildString — Score: 48,881,974.955 ops/s
mergeAlternatelyWithWhileLoop — Score: 34,447,752.568 ops/s
mergeAlternatelyWithZip — Score: 16,864,008.578 ops/s

mergeAlternatelyWithBuildString has the highest "Score," making it the fastest benchmark among the three.

Community Submissions 🌍

Community submissions are welcome to share your Kotlin writing style by solving this problem:

Sam Cooper from Kotlin Slack submitted his version — it works with vararg so you can send multiple strings, and it’s for fun 😄 :

fun mergeAlternately(vararg strings: String): String = buildString {
    val iterators = strings.map { it.iterator() }
    do {
        var shouldContinue = false
        for (iterator in iterators) {
            if (iterator.hasNext()) {
                append(iterator.nextChar())
                shouldContinue = true
            }
        }
    } while (shouldContinue)
}

Daniel Lin from Kotlin Slack submitted his two versions —

1. Version #1 : Using index to sort

fun mergeAlternately(word1: String, word2: String): String =
    (word1.withIndex() + word2.withIndex())
        .sortedBy { it.index }
        .joinToString("") { it.value.toString() }

2. Same as solution #2 but with function refrences

fun mergeAlternately(word1: String, word2: String): String = buildString {
    repeat(maxOf(word1.length, word2.length)) {
        word1.getOrNull(it)?.let(::append)
        word2.getOrNull(it)?.let(::append)
    }
}

and No so serious implementation :

suspend fun mergeAlternately(word1: String, word2: String): String = buildString {
    merge(
        word1.toList().asFlow().onEach { delay(99) },
        word2.toList().asFlow().onEach { delay(100) },
    ).collect(::append)
}

Pedro Pereira on Kotlin Slack submitted —

1. Instead of doing Max length he solves it with Min String and append remaining from long string.

fun mergeAlternately(word1: String, word2: String): String = buildString {
    val minLength = minOf(word1.length, word2.length)
    fun appendRemainder(word: String) {
        for(index in minLength..<word.length)
            append(word[index])
    }
    for(index in 0..<minLength) {
        append(word1[index])
        append(word2[index])
    }
    appendRemainder( if (minLength == word1.length) word2 else word1 )
}

Conclusion 💆🏻‍♀️

Hope you find it informative and if you like my content please don’t forget to check out my blogs and follow me on Twitter

AndroidBites

Until next time. Happy Hacking! 👩‍💻