Longest Common Prefix — Vertical Scan and Trie Approaches [Google Easy]

Problem Statement

Write a function to find the longest common prefix string among an array of strings. Return "" if there is none.

Input: ["flower","flow","flight"] → "fl" Input: ["dog","racecar","car"] → ""

Approach 1 — Vertical Scan (Column by Column)
Approach 2 — Horizontal Reduction
C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity: O(S) time where S = total characters, O(1) space

Approach 1 — Vertical Scan (Column by Column)

Check each character position across all strings simultaneously. Stop at the first mismatch or end of the shortest string.

for col = 0 to len(strs[0])-1:
    char = strs[0][col]
    for each string in strs:
        if col >= len(string) or string[col] != char:
            return strs[0][:col]
return strs[0]

Approach 2 — Horizontal Reduction

Start with prefix = strs[0]. For each subsequent string, shrink prefix until it matches the string's start.

C Solution

#include <string.h>
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    for (int col = 0; strs[0][col]; col++) {
        for (int i = 1; i < strsSize; i++) {
            if (!strs[i][col] || strs[i][col] != strs[0][col]) {
                strs[0][col] = '\0';
                return strs[0];
            }
        }
    }
    return strs[0];
}

C++ Solution

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        for (int col = 0; col < (int)strs[0].size(); col++) {
            char c = strs[0][col];
            for (int i = 1; i < (int)strs.size(); i++) {
                if (col >= (int)strs[i].size() || strs[i][col] != c) {
                    return strs[0].substr(0, col);
                }
            }
        }
        return strs[0];
    }
};

Java Solution

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
}

JavaScript Solution

function longestCommonPrefix(strs) {
    if (!strs.length) return '';
    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.slice(0, -1);
            if (!prefix) return '';
        }
    }
    return prefix;
}

Python Solution

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ''
        # Use zip to check column by column
        for i, chars in enumerate(zip(*strs)):
            if len(set(chars)) > 1:
                return strs[0][:i]
        return min(strs, key=len)

Complexity: O(S) time where S = total characters, O(1) space

Binary Search Approach: Binary search on prefix length 0..len(strs[0]). Check if prefix of that length is shared by all strings. O(S log m) where m = length of shortest string.