LeetCode Problem 14

Difficulty: 🟢 Easy
Topics: Array, String, Trie

Solution

LeetCode 14, Longest Common Prefix

Problem Understanding

The problem gives an array of strings and asks us to find the longest prefix shared by every string in the array.

A prefix is a sequence of characters that appears at the beginning of a string. For example, "fl" is a prefix of "flower" and "flow" because both strings start with those characters.

The task is to examine all strings and determine the longest sequence of starting characters that every string has in common. If the strings do not share even a single starting character, the answer should be an empty string "".

The input is an array of strings:

strs = ["flower", "flow", "flight"]

The expected output is:

"fl"

because all three strings begin with "fl".

The constraints are small:

• There can be at most 200 strings
• Each string can have length up to 200

This means even relatively straightforward solutions are fast enough. We do not need advanced optimization, but we still want a clean and efficient implementation.

Several edge cases are important:

• The array may contain only one string. In that case, the entire string is the answer.
• Some strings may be empty. If any string is empty, the longest common prefix must also be empty.
• The strings may share no common characters at all.
• One string may be completely contained inside another, such as ["car", "cart", "carbon"]. The shortest matching string limits the maximum possible prefix length.

A correct solution must stop as soon as a mismatch appears.

Approaches

Brute Force Approach

A brute force solution would generate every possible prefix from one of the strings and then check whether all other strings contain that prefix.

For example, if the first string is "flower", we could test:

"flower"
"flowe"
"flow"
"flo"
"fl"
"f"
""

For each prefix, we compare it against every other string. The first prefix that matches all strings is the answer.

This approach is correct because the longest common prefix must be a prefix of the first string. By checking prefixes from longest to shortest, the first valid one found must be the answer.

However, this repeatedly creates substrings and repeatedly scans strings, which introduces unnecessary overhead.

Optimal Approach

A better approach compares characters column by column.

The key observation is that a common prefix means:

All strings have the same character at the same index.

We can use the first string as a reference and iterate through its characters one by one.

At each character position:

• Compare the current character with the corresponding character in every other string.
• If any string is too short or has a different character, stop immediately.
• Everything before that position is the longest common prefix.

This works efficiently because we stop as soon as a mismatch appears, and every character is checked at most once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N × M²)	O(1) excluding substring creation	Tries many prefixes repeatedly
Optimal	O(N × M)	O(1)	Compares characters directly

Here:

• N is the number of strings
• M is the length of the shortest string

Algorithm Walkthrough

1. Start by taking the first string as the reference string.

Any common prefix must come from the beginning of this string, so it provides the characters we will test. 2. Iterate through each character index in the first string.

For example, if the first string is "flower", we examine:

index 0 -> 'f'
index 1 -> 'l'
index 2 -> 'o'
...

3. For every index, compare that character with the character at the same index in all other strings.

Two checks are necessary:

• If another string is shorter than the current index, the prefix cannot continue.
• If another string has a different character, the prefix also ends.

4. As soon as a mismatch occurs, return the substring from the beginning up to the current index.

This substring contains all matching characters discovered so far. 5. If the loop finishes without mismatches, return the entire first string.

That means every character matched across all strings.

Why it works

The algorithm maintains the invariant that all characters before the current index are identical across every string.

The moment a mismatch occurs, no longer prefix can exist because prefixes require every character position to match. Therefore, returning all characters before the mismatch guarantees the result is the longest valid common prefix.

Python Solution

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        first_string = strs[0]

        for index in range(len(first_string)):
            current_char = first_string[index]

            for string in strs[1:]:
                if index >= len(string) or string[index] != current_char:
                    return first_string[:index]

        return first_string

The implementation begins by storing the first string in first_string. This string acts as the reference for all comparisons.

The outer loop iterates through each character position in the reference string. At every index, the current character is stored in current_char.

The inner loop compares this character with the character at the same position in every other string.

The condition:

index >= len(string)

handles cases where another string is shorter than the current prefix length.

The condition:

string[index] != current_char

detects character mismatches.

If either condition becomes true, the algorithm immediately returns the prefix accumulated so far:

first_string[:index]

If the loop finishes successfully, the entire first string is common across all strings, so it is returned directly.

Go Solution

func longestCommonPrefix(strs []string) string {
    firstString := strs[0]

    for index := 0; index < len(firstString); index++ {
        currentChar := firstString[index]

        for i := 1; i < len(strs); i++ {
            currentString := strs[i]

            if index >= len(currentString) || currentString[index] != currentChar {
                return firstString[:index]
            }
        }
    }

    return firstString
}

The Go implementation follows the same logic as the Python version.

One notable difference is that Go strings are indexed as bytes. Since the problem guarantees lowercase English letters only, byte indexing is perfectly safe.

Go slices make substring extraction efficient:

firstString[:index]

This creates a substring view without manual copying.

The input constraints guarantee at least one string exists, so accessing strs[0] is safe.

Worked Examples

Example 1

Input:

["flower", "flow", "flight"]

Initial state:

Variable	Value
first_string	"flower"

Step-by-step execution

Index	Character	Compare With	Result
0	'f'	"flow"[0] = 'f'"	match
0	'f'	"flight"[0] = 'f'"	match
1	'l'	"flow"[1] = 'l'"	match
1	'l'	"flight"[1] = 'l'"	match
2	'o'	"flow"[2] = 'o'"	match
2	'o'	"flight"[2] = 'i'"	mismatch

At index 2, the mismatch occurs between 'o' and 'i'.

Return:

first_string[:2] = "fl"

Final answer:

"fl"

Example 2

Input:

["dog", "racecar", "car"]

Initial state:

Variable	Value
first_string	"dog"

Step-by-step execution

Index	Character	Compare With	Result
0	'd'	"racecar"[0] = 'r'"	mismatch

Mismatch occurs immediately at index 0.

Return:

first_string[:0] = ""

Final answer:

""

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N × M)	Each character is compared across all strings
Space	O(1)	Only a few variables are used

Here:

• N is the number of strings
• M is the length of the shortest string

The algorithm may inspect every character position of the common prefix across every string. Since no extra data structures proportional to input size are created, the space usage remains constant.

Test Cases

solution = Solution()

assert solution.longestCommonPrefix(
    ["flower", "flow", "flight"]
) == "fl"  # standard shared prefix

assert solution.longestCommonPrefix(
    ["dog", "racecar", "car"]
) == ""  # no common prefix

assert solution.longestCommonPrefix(
    ["apple"]
) == "apple"  # single string

assert solution.longestCommonPrefix(
    ["", "b"]
) == ""  # empty string present

assert solution.longestCommonPrefix(
    ["", ""]
) == ""  # all strings empty

assert solution.longestCommonPrefix(
    ["interview", "internet", "internal"]
) == "inte"  # longer shared prefix

assert solution.longestCommonPrefix(
    ["car", "cart", "carbon"]
) == "car"  # shortest string is prefix

assert solution.longestCommonPrefix(
    ["same", "same", "same"]
) == "same"  # identical strings

assert solution.longestCommonPrefix(
    ["a", "ab", "abc"]
) == "a"  # one-character prefix

assert solution.longestCommonPrefix(
    ["abc", "abd", "abe"]
) == "ab"  # mismatch near end

assert solution.longestCommonPrefix(
    ["prefix", "pre"]
) == "pre"  # second string shorter

assert solution.longestCommonPrefix(
    ["x", "y", "z"]
) == ""  # immediate mismatch

Test	Why
["flower", "flow", "flight"]	Standard example with partial prefix
["dog", "racecar", "car"]	No shared prefix
["apple"]	Single-element input
["", "b"]	Empty string handling
["", ""]	All strings empty
["interview", "internet", "internal"]	Longer shared prefix
["car", "cart", "carbon"]	One string completely contained
["same", "same", "same"]	Identical strings
["a", "ab", "abc"]	Very short prefix
["abc", "abd", "abe"]	Mismatch after multiple matches
["prefix", "pre"]	Shortest string determines answer
["x", "y", "z"]	Immediate mismatch at first character

Edge Cases

One important edge case occurs when one of the strings is empty. For example:

["", "abc"]

An empty string cannot contribute any characters to a common prefix, so the correct answer is immediately "". The implementation handles this naturally because the outer loop over the first string never executes if the first string is empty.

Another important case is when all strings are identical:

["test", "test", "test"]

A buggy implementation might stop too early or incorrectly trim the result. In this solution, every character comparison succeeds, so the algorithm returns the entire first string after the loop completes.

A third important edge case happens when one string is a complete prefix of another:

["car", "cartoon", "carpet"]

The correct answer is "car". The algorithm handles this correctly because it only iterates through characters of the first string. Once all characters in "car" are verified, the loop ends and the entire string is returned.

Another subtle case is when the mismatch happens at the very first character:

["abc", "xyz"]

The algorithm immediately detects the mismatch at index 0 and returns:

first_string[:0]

which correctly produces the empty string.