LESSON 163 OF 338 · LOOPS - CHALLENGES

Longest Common Prefix of Two Strings in Go: O(n) Scan

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

Guided

Ctrl + Enter to check

GO · LOOPS - CHALLENGES

Longest Common Prefix Of Two Strings in Go, explained

Problem overview

The function longestCommonPrefix receives two strings, s1 and s2, and returns the longest string that both of them start with. If they don't share a first character, the result is the empty string.

Three examples show the shapes the answer can take:

"hello" and "help" agree on h, e and l, then differ (l against p). The answer is "hel".
"Andy" and "Mircea" differ at the very first character, so the answer is "".
"AlgoCademy" and "Algo" agree on every character of the shorter string, so the answer is the whole shorter string, "Algo".

Approach: compare position by position

A common prefix is built from the left, so the first position where the strings differ ends it. Walk both strings together, index by index. While the characters match, add the character to the result. At the first mismatch, return what you have collected.

Two things bound the walk. The prefix can't be longer than the shorter string, so the loop must stop at the shorter length, otherwise it would read past the end of one string. And if the loop finishes without a mismatch, one string is a prefix of the other, and the answer is everything collected, which is the shorter string.

The scan looks at each position at most once, so the time is linear in the length of the shorter string.

Step by step

Find the limit. Declare n with := as the smaller of len(s1) and len(s2). Stopping there keeps every index valid in both strings.
Prepare the result. Declare commonPrefix as an empty string. It collects the matching characters.
Loop over the positions from 0 up to but not including n.
Stop at the first mismatch. If s1[i] differs from s2[i], return commonPrefix immediately. Nothing after a mismatch can belong to the prefix.
Keep the matching character. When the characters are equal, append one of them to commonPrefix. It doesn't matter which string it comes from.
Return after the loop. Reaching the end means all n characters matched, so return commonPrefix.

The solution in Go

func longestCommonPrefix(s1 string, s2 string) string {
    n := min(len(s1), len(s2))
    commonPrefix := ""
    for i := 0; i < n; i++ {
        if s1[i] != s2[i] {
            return commonPrefix
        }
        commonPrefix += string(s1[i])
    }
    return commonPrefix
}

The Go details that matter here:

Indexing a string gives a byte. s1[i] has type byte (an alias for uint8), the numeric value of the byte at position i, not a one-character string. For "hello", s1[0] is the number 104. Comparing two bytes with != is fine.
string(...) converts a byte to text. A byte can't be added to a string with +=, so string(s1[i]) turns the byte into a one-character string first. string(b) on a byte treats the number as a character code, so it is only right for ASCII text.
len counts bytes. For a string with non-ASCII characters, len is larger than the number of visible characters. len("héllo") is 6, because é takes two bytes in UTF-8. The lesson's inputs are ASCII, so byte positions and character positions coincide.
Built-in min. Since Go 1.21, min and max are built into the language and accept any ordered type, so no import is needed. Before 1.21 you would have written the comparison by hand.
Strings are immutable. commonPrefix += ... doesn't change the old string. It builds a new one containing the old text plus the new character and assigns that to the variable.
The zero value. A string variable with no value is "", and len("") is 0. An empty input therefore sets n to 0, the loop never runs, and the function returns "".

A non-ASCII caution

With non-ASCII text, converting single bytes breaks the result. string(s1[i]) on one byte of a multi-byte character doesn't recover that character: byte 195 becomes Ã, the character with code point 195. For text beyond ASCII, convert both strings to []rune and compare runes instead.

Complexity

Let m be the length of the shorter string.

Time: O(m), with a caveat. The loop runs at most m times and does constant work per pass besides the append. Because each += creates a new string and copies the old contents, a long prefix makes the copying add up to O(m²) in the worst case. For short strings this is invisible. If the prefix could be very long, return the slice s1[:i] at the mismatch (and s1[:n] at the end) instead of building a string one character at a time. That gives O(m) time without the repeated copying.

Space: O(m). The result string can be as long as the shorter input.

Edge cases and common mistakes

An empty string. longestCommonPrefix("", "x") returns "". Without the min limit, indexing the empty string would panic.
Identical strings. Every position matches, so the whole string comes back.
One string is a prefix of the other. The loop ends without a mismatch and the shorter string is returned, as in the "AlgoCademy" and "Algo" example.
Looping to the longer length. Using len(s1) as the bound crashes with an "index out of range" panic when s2 is shorter. Go checks every index at run time.
Skipping a mismatch instead of stopping. A loop that ignores a differing pair and keeps going would collect later matches. For "abcx" and "abyx" it would return "abx", which is not a prefix. The correct answer is "ab".
Case sensitivity. "Algo" and "algo" differ at the first character, because A and a are different bytes. The answer is "".

Testing

"hello", "help" gives "hel".
"Andy", "Mircea" gives "".
"AlgoCademy", "Algo" gives "Algo".
"", "x" gives "".
"abcx", "abyx" gives "ab".

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free