☕ DSA Java Articles

Topics › Strings › Basic and Easy String Problems

Longest Common Prefix

Easy TUF ID 395 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an array of strings strs, return the longest string that is a prefix of every string in the array. If the strings share no leading character, return the empty string "". For an empty array the answer is also "".

Constraints: 0 ≤ n ≤ 200 strings, each of length 0 to 200, lowercase English letters. The approaches below do not depend on the alphabet.

Example 1

strs = ["flower", "flow", "flight"]
answer = "fl"          // "flo" fails because of "flight"

Example 2

strs = ["dog", "racecar", "car"]
answer = ""            // d, r and c already differ in the first column

Example 3

strs = ["interspecies", "interstellar", "interstate"]
answer = "inters"

Approach 1: Brute force, test every prefix length

Intuition. The answer is a prefix of strs[0], and its length is at most the length of the shortest string. So there are only minLen + 1 candidates. Try them from the longest to the shortest and return the first one that every string starts with. Trying the longest first means the first success is the answer.

Algorithm.

  1. If the array is empty, return "".
  2. Compute minLen, the length of the shortest string.
  3. For len from minLen down to 1: let candidate = strs[0].substring(0, len); if every string startsWith(candidate), return it.
  4. Return "".
static String bruteForce(String[] strs) {
    if (strs.length == 0) return "";
    int minLen = Integer.MAX_VALUE;
    for (String s : strs) minLen = Math.min(minLen, s.length());
    for (int len = minLen; len >= 1; len--) {
        String candidate = strs[0].substring(0, len);
        boolean all = true;
        for (String s : strs) {
            if (!s.startsWith(candidate)) { all = false; break; }
        }
        if (all) return candidate;
    }
    return "";
}

Complexity. Time O(n · m^2) where m = minLen: up to m candidate lengths, each checked against n strings with an O(m) startsWith. Space O(m) for the current candidate.

Going from the longest candidate downwards is correct but wasteful: if the real answer is short, we check many long candidates that fail late. Checking from length 1 upwards and stopping at the first failure costs the same in the worst case but is faster in practice. Either way we re-compare the first characters over and over, which the optimal approach avoids.

Approach 2: Better, sort and compare the two extremes

Intuition. Sort the strings lexicographically. If the smallest string and the largest string share a prefix p, then every string in between shares it too: a string that did not start with p would, at its first deviating position, be either smaller than the minimum or larger than the maximum, which is impossible. So after sorting, only two strings need to be compared character by character.

Algorithm.

  1. If the array is empty, return "".
  2. Sort a copy of the array (do not mutate the caller’s input).
  3. Let first and last be the sorted extremes.
  4. Advance i while both strings have an i-th character and the characters match.
  5. Return first.substring(0, i).
static String better(String[] strs) {
    if (strs.length == 0) return "";
    String[] sorted = strs.clone();
    Arrays.sort(sorted);
    String first = sorted[0], last = sorted[sorted.length - 1];
    int i = 0;
    while (i < first.length() && i < last.length() && first.charAt(i) == last.charAt(i)) i++;
    return first.substring(0, i);
}

Complexity. Time O(n · m log n) for the sort, where each comparison is O(m), plus O(m) for the final scan. Space O(n) for the copied array.

Sorting is heavier than necessary for this problem, but the “compare the extremes” trick is useful when the strings are already sorted (for example keys of a TreeMap), where it gives an O(m) answer without looking at the middle strings at all.

Approach 3: Optimal, vertical scan with early exit

Intuition. Think of the strings written one below another. The common prefix is the set of leading columns in which every character is identical. Walk column by column: for column i, compare strs[0].charAt(i) with the same column in every other string. The moment a string is too short or has a different character, columns 0..i-1 are the answer. This stops at the first mismatch and never re-reads a character, which is what the brute force was missing.

Algorithm.

  1. If the array is empty, return "".
  2. For i from 0 to strs[0].length() - 1: let c = strs[0].charAt(i).
  3. For every other string k: if i == strs[k].length() or strs[k].charAt(i) != c, return strs[0].substring(0, i).
  4. If the outer loop finishes, strs[0] is a prefix of everything; return it.
static String optimal(String[] strs) {
    if (strs.length == 0) return "";
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int k = 1; k < strs.length; k++) {
            if (i == strs[k].length() || strs[k].charAt(i) != c) return strs[0].substring(0, i);
        }
    }
    return strs[0];
}

Dry run on ["flower", "flow", "flight"]:

i c = strs[0][i] flow[i] flight[i] result
0 f f f continue
1 l l l continue
2 o o i mismatch, return "fl"

Complexity. Time O(S) in the worst case, where S is the total number of characters (all strings identical); in general O(n · L) where L is the answer length plus one. Space O(1) extra beyond the returned prefix.

The order of the two conditions in the if is essential: i == strs[k].length() must be tested before strs[k].charAt(i), otherwise a shorter string throws StringIndexOutOfBoundsException. Java’s || short-circuits, so the second operand is not evaluated when the first is true.

A horizontal variant is equally good: start with prefix = strs[0] and, for each following string, shorten prefix until the string starts with it. Both are O(S); the vertical one simply exits earlier when the mismatch is in an early column.

Edge cases and pitfalls