Start learning free

LESSON 163 OF 348 · LOOPS - CHALLENGES

Longest Common Prefix of Two Strings in Kotlin

Practice Read the full explanation

Given two strings s1 and s2, return their longest common prefix

Example 1:

Input:  s1 = "hello", s2 = "help"
Output:  "hel"

Example 2:

Input:  s1 = "Andy", s2 = "Mircea"
Output:  ""

Example 3:

Input:  s1 = "AlgoCademy", s2 = "Algo"
Output:  "Algo"

STEP 1 OF 6
    Ctrl + Enter to check

    KOTLIN · LOOPS - CHALLENGES

    Longest Common Prefix Of Two Strings in Kotlin, explained

    Problem overview

    The function longestCommonPrefix(s1: String, s2: String) returns the longest string that both inputs start with. A prefix is a beginning of a string, so the common prefix is the run of characters at the start that match in both.

    The examples show the three kinds of result. For "hello" and "help" the first three characters match (h, e, l) and the fourth differs (l against p), so the answer is "hel". For "Andy" and "Mircea" the very first characters differ, so the answer is the empty string "". For "AlgoCademy" and "Algo" the shorter string is entirely a prefix of the longer one, so the answer is "Algo".

    Approach

    Compare the two strings position by position from the left. While the characters at the same index are equal, the prefix keeps growing. At the first index where they differ, the prefix ends: no later match can extend it, because a prefix has to be unbroken from the start. So the loop can stop at that point.

    There is one more limit. The loop can't look at an index that one of the strings doesn't have. The prefix is at most as long as the shorter string, so the loop runs only up to the shorter length.

    Step by step

    1. Find the shorter length. val n = minOf(s1.length, s2.length) gives the number of positions that exist in both strings. In Kotlin, length is a property, so there are no parentheses.
    2. Start with an empty prefix. var commonPrefix = "" is a var because it grows during the loop.
    3. Loop over the shared positions. for (i in 0 until n) visits indices 0 to n - 1. The until range excludes its upper end, which is what indexing needs.
    4. Stop at the first difference. If s1[i] != s2[i], call break to leave the loop. Indexing a string with [i] gives a Char, so != compares two characters.
    5. Extend the prefix. Code after the if only runs when the characters matched, so commonPrefix += s1[i] adds that character. Either string would do, since they hold the same character here.
    6. Return the result. The return after the loop covers both ways of leaving it: a break at a mismatch, or the end of the range when the shorter string is a prefix of the longer one.

    The solution in Kotlin

    class Solution {
    fun longestCommonPrefix(s1: String, s2: String): String {
        val n = minOf(s1.length, s2.length)
        var commonPrefix = ""
        for (i in 0 until n) {
            if (s1[i] != s2[i]) {
                break
            }
            commonPrefix += s1[i]
        }
        return commonPrefix
    }
}

    Kotlin details:

    • val and var. n never changes, so it is a val. commonPrefix is reassigned in the loop, so it is a var.
    • Strings are immutable. commonPrefix += s1[i] doesn't change the old string. It creates a new, longer string made of the old text plus the Char, and the variable now refers to it.
    • String + Char works. Adding a Char to a String with + gives a String. Writing + between two Char values does not join them into a string, so keep the string on the left.
    • Comparison with !=. On Char values it compares the characters. On strings, == and != compare contents, not references.
    • break. It ends the innermost loop immediately, and execution continues at the line after the loop.

    A shorter way to build the result

    Instead of growing a string, the loop can remember how many characters matched and cut the answer once at the end. The lesson builds the prefix character by character because it shows the idea directly: each match adds one character, and the first mismatch stops the process. Whichever form you use, the loop condition and the break are what make the answer correct.

    Complexity

    Let m be the length of the shorter string.

    Time: O(m) comparisons, one per matching position plus at most one failing comparison. Because += copies the growing string each time, the total copying can reach O(m²) for a long prefix. For short strings this doesn't matter. To keep it linear, use s1.substring(0, i) once at the end, or a StringBuilder.

    Space: O(m) for the result, which can be as long as the shorter input. Beyond the result the loop uses a few variables.

    Edge cases and common mistakes

    • An empty string. If either input is empty, n is 0, the loop doesn't run, and the function returns "".
    • Identical strings. Every position matches and the whole string comes back. "same" and "same" give "same".
    • Using the longer length. Looping to s1.length reads past the end of the shorter string. Indexing a Kotlin string out of range throws a StringIndexOutOfBoundsException, which is why the loop uses the minimum.
    • Forgetting break. Without it, the loop only skips the mismatched position and carries on, so later matching characters are added after the gap. With "abxd" and "abyd" the result would be "abd" instead of "ab". A prefix can't have a gap, which is why the first mismatch must end the loop.
    • Case. Characters are compared exactly. 'A' and 'a' are different, so "Algo" and "algo" have an empty common prefix.
    • Using .. instead of until. 0..n includes n, which is one past the last valid index of the shorter string.

    Testing

    • "hello", "help" gives "hel".
    • "Andy", "Mircea" gives "".
    • "AlgoCademy", "Algo" gives "Algo".
    • "", "x" gives "".
    • "abxd", "abyd" gives "ab".
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free