Longest Common Prefix of Strings

Given an array of strings arr. Return the longest common prefix among all strings present in the array. If there’s no prefix common in all the strings, return “-1“.

Examples :

Input: arr[] = ["geeksforgeeks", "geeks", "geek", "geezer"]
Output: gee
Explanation: "gee" is the longest common prefix in all the given strings.

Input: arr[] = ["hello", "world"]
Output: -1
Explanation: There's no common prefix in the given strings.

Expected Time Complexity: O(n*min(|arr_i|))
Expected Space Complexity: O(min(|arr_i|))

Constraints:
1 ≤ |arr| ≤ 10³
1 ≤ |arr[i]| ≤ 10³

Approach 01:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector<string>& strings) {
        int numStrings = strings.size();

        // Sort the vector of strings
        sort(strings.begin(), strings.end());

        // Take the first string as the reference for finding the common prefix
        int referenceLength = strings[0].length();
        string referenceString = strings[0];
        string commonPrefix = "";

        // Iterate through the characters of the reference string
        for (int i = 1; i <= referenceLength; ++i) {
            string currentPrefix = referenceString.substr(0, i);
            bool isCommonPrefix = true;

            // Check if the current prefix is common to all strings
            for (int j = 1; j < numStrings; ++j) {
                if (strings[j].substr(0, i) != currentPrefix) {
                    isCommonPrefix = false;
                    break;
                }
            }

            // If the current prefix is common to all strings, update the result
            if (isCommonPrefix) {
                commonPrefix = currentPrefix;
            }
        }

        // If no common prefix is found, return "-1"
        if (commonPrefix.length() == 0) {
            return "-1";
        }

        return commonPrefix;
    }
};

from typing import List

class Solution:
    def longestCommonPrefix(self, strings: List[str]) -> str:
        numStrings = len(strings)

        # Sort the list of strings
        strings.sort()

        # Take the first string as the reference for finding the common prefix
        referenceLength = len(strings[0])
        referenceString = strings[0]
        commonPrefix = ""

        # Iterate through the characters of the reference string
        for i in range(1, referenceLength + 1):
            currentPrefix = referenceString[:i]
            isCommonPrefix = True

            # Check if the current prefix is common to all strings
            for j in range(1, numStrings):
                if strings[j][:i] != currentPrefix:
                    isCommonPrefix = False
                    break

            # If the current prefix is common to all strings, update the result
            if isCommonPrefix:
                commonPrefix = currentPrefix

        # If no common prefix is found, return "-1"
        if len(commonPrefix) == 0:
            return "-1"

        return commonPrefix

Time Complexity

• Sorting the Vector of Strings:

  Sorting the vector of strings takes \( O(n \log n) \) time, where \( n \) is the number of strings in the input vector.

• Finding the Longest Common Prefix:

  Finding the longest common prefix involves iterating through the characters of the shortest string and comparing each character with the corresponding character in all other strings. In the worst case, this takes \( O(n \cdot m) \) time, where \( m \) is the length of the shortest string and \( n \) is the number of strings.

• Overall Time Complexity:

  The overall time complexity is \( O(n \log n + n \cdot m) \), where \( n \) is the number of strings and \( m \) is the length of the shortest string.

Space Complexity

• Space for Sorting:

  The sorting operation does not require any additional space other than the input vector itself, so it uses \( O(1) \) additional space.

• Space for Storing the Common Prefix:

  The space required for storing the common prefix is \( O(m) \), where \( m \) is the length of the shortest string.

• Overall Space Complexity:

  The overall space complexity is \( O(m) \), where \( m \) is the length of the shortest string.