14 Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

In my opinion this problem statement isn't very clear. What are we prioritizing? The longest, or the most common? Because obviously the most common is going to be the shortest prefix, and the longest is going to be the least common.

This clarified it for me:

It seems that it is not to check between pair of strings but on all the strings in the array.

For example:

1. {"a","a","b"} should give "" as there is nothing common in all the 3 strings.

2. {"a", "a"} should give "a" as a is longest common prefix in all the strings.

3. {"abca", "abc"} as abc

4. {"ac", "ac", "a", "a"} as a.

• Brute force approach: map every possible substring prefix from the word, and generate all the frequencies.

• The most frequent word that is also just as or greater in length is the max common prefix.

• Order is not preserved! (elements that are just as frequent will overwrite the previous). Using unordered_map.

string map_max(unordered_map<string, int> &map) {
    int max = INT_MIN;
    string max_string = "";
    for (auto &i : map) {
        if (i.second >= max && i.first.length() >= max_string.length()) {
            max = i.second;
            max_string = i.first;
        }
    }
    return max_string;
}

string longestCommonPrefix(vector<string>& strs) {
    if (strs.size() == 0)
        return "";

    unordered_map<string, int> str_freq;

    for (int i = 0; i < strs.size(); i++) {
        string word = strs.at(i);
        for (int j = 0; j < word.length(); j++) {
            string sub = word.substr(0, j + 1);

            if (str_freq.find(sub) != str_freq.end()) {
                str_freq.find(sub)->second++;
            }
            else {
                // not found
                str_freq.insert({ { sub },{ 1 } });
            }
        }
    }

    return map_max(str_freq);
}


int main() {
    vector<string> strs = {""};
    cout << longestCommonPrefix(strs) << endl;
    pause();

    strs = { "a", "b", "c" };
    cout << longestCommonPrefix(strs) << endl;
    pause();

    strs = { "ab", "ab", "cc" };
    cout << longestCommonPrefix(strs) << endl;
    pause();

    strs = { "abc", "abc", "abcd", "abcde", "ac", "ac", "ac" };
    cout << longestCommonPrefix(strs) << endl;
    pause();

    strs = { "abc", "abc", "abcd", "abcde", "ac", "ac", "ac", "abcde","abcde","abcde","abcde","abcde","abcde",
            "bca", "bca","bca","bca","bca","bca","bca","bca","bca","bca","bca","bca","bca","bca","bca", };
    cout << longestCommonPrefix(strs) << endl;
    pause();
}

Improved Python Solution

The Idea: Sort the array of strings and compare the first and last strings. This works because 1) all words have the share the common prefix, and 2) sorting ensures that the two most distant words by prefix, (which the definition of the sort) are compared. In other words, there is no need to compare the n-1th word to the first, because we'd have to confirm with the last word anyway. Additionally, the n-1th word is going to share a larger or same common prefix with the last word, relative to the first word. And since all words have to be in common, the last word will determine what is most common and longest.

Complexity: O(nlogn + n) time and O(1) space

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        if not strs: return ''
        elif len(strs) == 1: return strs[0]

        strs = sorted(strs)
        s1 = strs[0]
        s2 = strs[-1]

        solution = ''
        iter = 0
        while iter < len(s1) and iter < len(s2):
            if s1[iter] != s2[iter]:
                return solution
            else:
                solution += s1[iter]
            iter += 1
        return solution