Longest Common Prefix of Strings

JavaView on GFG

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?