Longest Common Prefix of Strings

JavaView on GFG

Problem Overview

Find longest common prefix of all strings.

Intuition

Find longest common prefix of all strings. Vertical scan or sort and compare first/last.

Algorithm

1Sort array. LCP of entire array = LCP of first and last string (they differ most after sorting).

Common Pitfalls

• Same as LC 14. Sort trick reduces to comparing just first and last. O(n log n + m) where m=prefix length.

Longest Common Prefix of Strings.java

Java

// Approach: Sort strings, then compare only first and last in sorted order character by character.
// Time: O(n log n * len) Space: O(1)
import java.util.*;

class Solution {
    public String longestCommonPrefix(String arr[]) {
        Arrays.sort(arr);
        int n = arr.length;
        String first = arr[0], last = arr[n - 1];

        if (first.charAt(0) != last.charAt(0))
            return "-1";

        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < first.length() && i < last.length()) {
            if (first.charAt(i) == last.charAt(i))
                sb.append(first.charAt(i));
            else
                return sb.toString();

            i++;
        }

        return sb.toString();
    }
}

Was this solution helpful?