NUHMAN.com

Introduction

LeetCode 14: Longest Common Prefix is a beginner-friendly yet fundamental string problem. It requires you to find the longest prefix that is shared by all strings in an array.

In this article, we’ll look at an efficient vertical scanning approach and implement it neatly in Go (Golang).

Problem Statement

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Examples

go

Input: strs = ["flower","flow","flight"]
Output: "fl"
go

Input: strs = ["dog","racecar","car"]
Output: ""

Constraints

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• All strings consist of lowercase English letters.

Approach: Vertical Scanning

We compare characters column-by-column (vertical scan) from the beginning of the strings:

• Pick the first string as the baseline.
• At each character index i, check whether all strings have the same character.
• Stop as soon as a mismatch or end of a string is found.

Why this works:

It’s simple and efficient because we stop as soon as we hit a mismatch.

Go Implementation

go

package main

import (
    "fmt"
)

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }

    for i := 0; i < len(strs[0]); i++ {
        char := strs[0][i]
        for j := 1; j < len(strs); j++ {
            if i >= len(strs[j]) || strs[j][i] != char {
                return strs[0][:i]
            }
        }
    }

    return strs[0]
}

func main() {
    testCases := [][]string{
        {"flower", "flow", "flight"},
        {"dog", "racecar", "car"},
        {"interview", "internet", "internal"},
        {"", "anything"},
        {"abc"},
    }

    for _, strs := range testCases {
        fmt.Printf("Input: %v -> Longest Common Prefix: '%s'\n", strs, longestCommonPrefix(strs))
    }
}

Step-by-Step Example: ["flower","flow","flight"]

1. Compare column 0 → f == f == f → ✅
2. Compare column 1 → l == l == l → ✅
3. Compare column 2 → o == o == i → ❌ Mismatch → Stop

Result: "fl"

Time and Space Complexity

• Time Complexity: O(S), where S is the sum of all characters in all strings (in the worst case).
• Space Complexity: O(1), ignoring the output string.

Alternate Approaches

• Horizontal Scanning: Start with the first word as prefix, compare with others and shorten.
• Divide & Conquer: Recursively find common prefixes of halves and merge.
• Trie-based: Optimal for very large datasets (but overkill here).

Key Takeaways

• Vertical scanning is perfect when dealing with short to mid-length strings.
• Early exit on mismatch boosts performance.
• String problems often benefit from choosing the right perspective — row-wise vs. column-wise.