14. Longest Common Prefix - Solution & Code

Q: Is Longest Common Prefix easy or hard?

Longest Common Prefix is categorized as an Easy problem. The core idea is straightforward string comparison, but interviewers expect candidates to reason about efficiency and avoid redundant comparisons across multiple strings.

Q: Longest Common Prefix Python/Java solution

In Python or Java, the common implementation uses horizontal scanning. Start with the first string as the prefix and repeatedly shorten it until each string begins with that prefix using substring or startsWith checks. This approach runs in O(S) time and constant extra space.

Q: How to solve Longest Common Prefix in O(n)?

Treat n as the total number of characters processed across all strings. Use horizontal scanning: keep a candidate prefix and shrink it whenever the current string does not start with that prefix. Since each character is examined only once, the overall complexity remains linear in the total character count.

Q: What is the best approach for Longest Common Prefix?

Horizontal scanning is the most commonly used approach. Start with the first string as the prefix and iteratively shrink it until it matches the start of every other string. The method runs in O(S) time, where S is the total number of characters across all strings, and uses O(1) extra space.

Q: Is Longest Common Prefix asked at Google/Amazon/Meta?

Longest Common Prefix frequently appears in coding interviews at companies like Amazon, Google, and Meta as an introductory string problem. It tests basic string manipulation, iteration patterns, and understanding of algorithmic complexity.

Q: What data structure is used in Longest Common Prefix?

Most solutions rely only on basic string operations. A Trie can also be used by inserting all strings and walking down nodes while only one child exists. The Trie approach is helpful for learning prefix trees but is usually unnecessary for a single query.

Q: What is the time complexity of Longest Common Prefix?

The optimal solutions run in O(S) time, where S represents the total number of characters across all input strings. Each character is compared at most once during prefix checks. Space complexity is O(1) for horizontal scanning and higher for recursive or Trie-based methods.

The problem

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 "".

Example 1:

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

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

Approach overview

Problem Overview: Given an array of strings, return the longest prefix shared by every string. If the strings have no common starting characters, return an empty string. The challenge is efficiently comparing characters across multiple strings without unnecessary repeated work.

Approach 1: Horizontal Scanning (Time: O(S), Space: O(1))

Start with the first string as the candidate prefix. Iterate through the remaining strings and shrink the prefix until it matches the start of the current string. This works by repeatedly checking whether strs[i].startsWith(prefix); if not, remove the last character from the prefix and try again. The key insight: the prefix can only become shorter as you compare more strings. Since each character across all strings is examined at most once, the total cost is proportional to the total number of characters S. This approach uses simple iteration over the array and is the most practical solution for typical string interview problems.

Approach 2: Divide and Conquer (Time: O(S), Space: O(m log n))

Treat the problem similarly to merge operations. Split the array of strings into two halves, recursively compute the longest common prefix for each half, then merge the results by comparing characters of the two prefixes. The merge step scans character by character until a mismatch occurs. The insight is that computing prefixes for smaller groups reduces redundant comparisons across the entire list. This approach uses divide and conquer with recursion and performs the same total amount of character comparisons as horizontal scanning, resulting in O(S) time where S is the total number of characters across all strings.

Approach 3: Trie-Based Prefix Search (Time: O(S), Space: O(S))

Insert all strings into a Trie. After construction, walk down the Trie from the root while there is exactly one child and the node is not marked as the end of a word. Each step represents a shared prefix character. The traversal stops when branching occurs or a word terminates. The collected characters form the longest common prefix. While conceptually clean and useful when solving multiple prefix queries, it requires additional memory proportional to the total characters stored.

Recommended for interviews: Horizontal scanning is the expected answer in most interviews because it is simple, readable, and runs in optimal O(S) time with constant extra space. Divide and conquer demonstrates stronger algorithmic thinking and recursion skills. A Trie solution is rarely required but shows deeper knowledge of prefix-based data structures.

Approach 1: Horizontal Scanning

In this approach, you start with the first string as a reference and gradually compare it with each subsequent string in the array. The reference prefix is shortened until it matches the prefixes of all strings.

Python

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        prefix = strs[0]
        for s in strs[1:]:
            while not s.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix

if __name__ == "__main__":
    sol = Solution()
    print(sol.longestCommonPrefix(["flower", "flow", "flight"]))

Java

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] strs = { "flower", "flow", "flight" };
        System.out.println(sol.longestCommonPrefix(strs));
    }
}

C++

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

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];
    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

int main() {
    vector<string> strs = { "flower", "flow", "flight" };
    cout << longestCommonPrefix(strs) << endl;
    return 0;
}

JavaScript

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

console.log(longestCommonPrefix(["flower", "flow", "flight"]));

#include <stdio.h>
#include <string.h>

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    char* prefix = strs[0];
    for (int i = 1; i < strsSize; i++) {
        while (strstr(strs[i], prefix) != strs[i]) {
            prefix[strlen(prefix) - 1] = '\0';
            if (*prefix == '\0') return "";
        }
    }
    return prefix;
}

int main() {
    char *strs[] = { "flower", "flow", "flight" };
    printf("%s\n", longestCommonPrefix(strs, 3));
    return 0;
}

using System;
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].IndexOf(prefix) != 0) {
                prefix = prefix.Substring(0, prefix.Length - 1);
                if (prefix == "") return "";
            }
        }
        return prefix;
    }

    static void Main(string[] args) {
        var sol = new Solution();
        string[] strs = { "flower", "flow", "flight" };
        Console.WriteLine(sol.LongestCommonPrefix(strs));
    }
}

Python readily facilitates string manipulation. Using startswith, we efficiently trim the prefix for each string until a match is found or it becomes empty.

Complexity

Time Complexity: O(S).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Divide and Conquer

This approach involves dividing the array of strings into two halves, recursively finding the longest common prefix for each half, and merging the results. The merge step compares characters from the two strings to find the common prefix.

Python

class Solution:
    def commonPrefix(self, left, right):
        minLength = min(len(left), len(right))
        for i in range(minLength):
            if left[i] != right[i]:
                return left[:i]
        return left[:minLength]

    def divideAndConquer(self, strs, left, right):
        if left == right:
            return strs[left]
        else:
            mid = (left + right) // 2
            lcpLeft = self.divideAndConquer(strs, left, mid)
            lcpRight = self.divideAndConquer(strs, mid + 1, right)
            return self.commonPrefix(lcpLeft, lcpRight)

    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        return self.divideAndConquer(strs, 0, len(strs) - 1)

if __name__ == "__main__":
    sol = Solution()
    print(sol.longestCommonPrefix(["flower", "flow", "flight"]))

Java

class Solution {
    private String commonPrefix(String left, String right) {
        int minLength = Math.min(left.length(), right.length());
        for (int i = 0; i < minLength; i++) {
            if (left.charAt(i) != right.charAt(i)) {
                return left.substring(0, i);
            }
        }
        return left.substring(0, minLength);
    }

    private String divideAndConquer(String[] strs, int left, int right) {
        if (left == right) {
            return strs[left];
        } else {
            int mid = (left + right) / 2;
            String lcpLeft = divideAndConquer(strs, left, mid);
            String lcpRight = divideAndConquer(strs, mid + 1, right);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return divideAndConquer(strs, 0, strs.length - 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] strs = { "flower", "flow", "flight" };
        System.out.println(sol.longestCommonPrefix(strs));
    }
}

C++

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

string commonPrefix(string left, string right) {
    int minLength = min(left.size(), right.size());
    for (int i = 0; i < minLength; i++) {
        if (left[i] != right[i]) {
            return left.substr(0, i);
        }
    }
    return left.substr(0, minLength);
}

string divideAndConquer(vector<string>& strs, int left, int right) {
    if (left == right) {
        return strs[left];
    } else {
        int mid = (left + right) / 2;
        string lcpLeft = divideAndConquer(strs, left, mid);
        string lcpRight = divideAndConquer(strs, mid + 1, right);
        return commonPrefix(lcpLeft, lcpRight);
    }
}

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    return divideAndConquer(strs, 0, strs.size() - 1);
}

int main() {
    vector<string> strs = { "flower", "flow", "flight" };
    cout << longestCommonPrefix(strs) << endl;
    return 0;
}

JavaScript

function commonPrefix(left, right) {
    const minLength = Math.min(left.length, right.length);
    for (let i = 0; i < minLength; i++) {
        if (left[i] !== right[i]) {
            return left.substring(0, i);
        }
    }
    return left.substring(0, minLength);
}

function divideAndConquer(strs, left, right) {
    if (left === right) {
        return strs[left];
    } else {
        const mid = Math.floor((left + right) / 2);
        const lcpLeft = divideAndConquer(strs, left, mid);
        const lcpRight = divideAndConquer(strs, mid + 1, right);
        return commonPrefix(lcpLeft, lcpRight);
    }
}

function longestCommonPrefix(strs) {
    if (!strs.length) return "";
    return divideAndConquer(strs, 0, strs.length - 1);
}

console.log(longestCommonPrefix(["flower", "flow", "flight"]));

#include <stdio.h>
#include <string.h>

char* commonPrefix(char* left, char* right) {
    int minLength = strlen(left) < strlen(right) ? strlen(left) : strlen(right);
    for (int i = 0; i < minLength; i++) {
        if (left[i] != right[i]) {
            left[i] = '\0';
            break;
        }
    }
    return left;
}

char* divideAndConquer(char** strs, int left, int right) {
    if (left == right) {
        return strs[left];
    } else {
        int mid = (left + right) / 2;
        char* lcpLeft = divideAndConquer(strs, left, mid);
        char* lcpRight = divideAndConquer(strs, mid + 1, right);
        return commonPrefix(lcpLeft, lcpRight);
    }
}

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    return divideAndConquer(strs, 0, strsSize - 1);
}

int main() {
    char *strs[] = { "flower", "flow", "flight" };
    printf("%s\n", longestCommonPrefix(strs, 3));
    return 0;
}

using System;

class Solution {
    private string CommonPrefix(string left, string right) {
        int minLength = Math.Min(left.Length, right.Length);
        for (int i = 0; i < minLength; i++) {
            if (left[i] != right[i]) {
                return left.Substring(0, i);
            }
        }
        return left.Substring(0, minLength);
    }

    private string DivideAndConquer(string[] strs, int left, int right) {
        if (left == right) {
            return strs[left];
        } else {
            int mid = (left + right) / 2;
            string lcpLeft = DivideAndConquer(strs, left, mid);
            string lcpRight = DivideAndConquer(strs, mid + 1, right);
            return CommonPrefix(lcpLeft, lcpRight);
        }
    }

    public string LongestCommonPrefix(string[] strs) {
        if (strs == null || strs.Length == 0) return "";
        return DivideAndConquer(strs, 0, strs.Length - 1);
    }

    static void Main(string[] args) {
        var sol = new Solution();
        string[] strs = { "flower", "flow", "flight" };
        Console.WriteLine(sol.LongestCommonPrefix(strs));
    }
}

Python divides & conquers recursively to manage string partitions, aligning with common prefix checks for efficiency and scalability.

Complexity

Time Complexity: O(S).
Space Complexity: O(M*logN).

Try this approach in the editor

Approach 3: Character Comparison

We use the first string strs[0] as a benchmark, and compare whether the i-th character of the subsequent strings is the same as the i-th character of strs[0]. If they are the same, we continue to compare the next character. Otherwise, we return the first i characters of strs[0].

If the traversal ends, it means that the first i characters of all strings are the same, and we return strs[0].

The time complexity is O(n times m), where n and m are the length of the string array and the minimum length of the strings, respectively. The space complexity is O(1).

TypeScript

function longestCommonPrefix(strs: string[]): string {
    const len = strs.reduce((r, s) => Math.min(r, s.length), Infinity);
    for (let i = len; i > 0; i--) {
        const target = strs[0].slice(0, i);
        if (strs.every(s => s.slice(0, i) === target)) {
            return target;
        }
    }
    return '';
}

func longestCommonPrefix(strs []string) string {
	n := len(strs)
	for i := range strs[0] {
		for j := 1; j < n; j++ {
			if len(strs[j]) <= i || strs[j][i] != strs[0][i] {
				return strs[0][:i]
			}
		}
	}
	return strs[0]
}

Rust

impl Solution {
    pub fn longest_common_prefix(strs: Vec<String>) -> String {
        let mut len = strs.iter().map(|s| s.len()).min().unwrap();
        for i in (1..=len).rev() {
            let mut is_equal = true;
            let target = strs[0][0..i].to_string();
            if strs.iter().all(|s| target == s[0..i]) {
                return target;
            }
        }
        String::new()
    }
}

Ruby

# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
  return '' if strs.nil? || strs.length.zero?

  return strs[0] if strs.length == 1

  idx = 0
  while idx < strs[0].length
    cur_char = strs[0][idx]

    str_idx = 1
    while str_idx < strs.length
      return idx > 0 ? strs[0][0..idx-1] : '' if strs[str_idx].length <= idx

      return '' if strs[str_idx][idx] != cur_char && idx.zero?
      return strs[0][0..idx - 1] if strs[str_idx][idx] != cur_char
      str_idx += 1
    end

    idx += 1
  end

  idx > 0 ? strs[0][0..idx] : ''
end

PHP

class Solution {
    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        $rs = '';
        for ($i = 0; $i < strlen($strs[0]); $i++) {
            for ($j = 1; $j < count($strs); $j++) {
                if ($strs[0][$i] != $strs[$j][$i]) {
                    return $rs;
                }
            }
            $rs = $rs . $strs[0][$i];
        }
        return $rs;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Horizontal Scanning	Time Complexity: O(S). Space Complexity: O(1).
Divide and Conquer	Time Complexity: O(S). Space Complexity: O(M*logN).
Character Comparison	–

Complexity analysis

Approach	Time	Space	When to Use
Horizontal Scanning	O(S)	O(1)	Best general solution. Simple iteration across strings with minimal memory.
Divide and Conquer	O(S)	O(m log n)	Useful when practicing recursive problem decomposition.
Trie-Based Approach	O(S)	O(S)	Helpful when many prefix queries are required on the same dataset.

Frequently asked questions

Is Longest Common Prefix easy or hard?

Longest Common Prefix is categorized as an Easy problem. The core idea is straightforward string comparison, but interviewers expect candidates to reason about efficiency and avoid redundant comparisons across multiple strings.

Longest Common Prefix Python/Java solution

In Python or Java, the common implementation uses horizontal scanning. Start with the first string as the prefix and repeatedly shorten it until each string begins with that prefix using substring or startsWith checks. This approach runs in O(S) time and constant extra space.

How to solve Longest Common Prefix in O(n)?

Treat n as the total number of characters processed across all strings. Use horizontal scanning: keep a candidate prefix and shrink it whenever the current string does not start with that prefix. Since each character is examined only once, the overall complexity remains linear in the total character count.

What is the best approach for Longest Common Prefix?

Horizontal scanning is the most commonly used approach. Start with the first string as the prefix and iteratively shrink it until it matches the start of every other string. The method runs in O(S) time, where S is the total number of characters across all strings, and uses O(1) extra space.

Is Longest Common Prefix asked at Google/Amazon/Meta?

Longest Common Prefix frequently appears in coding interviews at companies like Amazon, Google, and Meta as an introductory string problem. It tests basic string manipulation, iteration patterns, and understanding of algorithmic complexity.

What data structure is used in Longest Common Prefix?

Most solutions rely only on basic string operations. A Trie can also be used by inserting all strings and walking down nodes while only one child exists. The Trie approach is helpful for learning prefix trees but is usually unnecessary for a single query.

What is the time complexity of Longest Common Prefix?

The optimal solutions run in O(S) time, where S represents the total number of characters across all input strings. Each character is compared at most once during prefix checks. Space complexity is O(1) for horizontal scanning and higher for recursive or Trie-based methods.

Longest Common Prefix solution and explanation

The problem

Approach overview

Approach 1: Horizontal Scanning

Approach 2: Divide and Conquer

Approach 3: Character Comparison

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Common Prefix solution and explanation

The problem

Approach overview

Approach 1: Horizontal Scanning

Approach 2: Divide and Conquer

Approach 3: Character Comparison

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems