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

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = [“flower”,”flow”,”flight”]

Output: “fl”

Example 2:

Input: strs = [“dog”,”racecar”,”car”]

Output: “”

Explanation: There is no common prefix among the input strings.

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

Solution

Intuition

Sort and check for the matching common prefix among the elements.
Sorting will arrange in alphabetical order, so traversing to find the common prefix will be between each two elements can be avioded.

Approach

We are to find the longest common substring, for which, it is supposed that each element will have atleast one common prefix or none at all.

Steps:

1. Sort the given array of strings,
2. Declare and initialize a counter to count the length of the common prefix,
3. Find out the minimum among the lenght of the FIRST and LAST element of the sorted string.
4. Run a loop till the counter is less than the minimum length.
5. Traverse the characters of the first and the last string to find out the longest common prefix, and increment the counter likewise,
6. Return the substring of the length of the counter.

Complexity

• Time complexity:O(n log n)
• Space complexity: O(1)

class Solution {
public:
    string longestCommonPrefix(vector<string>& s) {
        sort(s.begin(),s.end());
        int c=0, 
        minLen=min(s[0].size(),s[s.size()-1].size());
        while(c<minLen)
            if(s[0][c]==s[s.size()-1][c])
                c++;
            else
                break;
        return s[0].substr(0,c);
    }
};

class Solution {
    public String longestCommonPrefix(String[] s) {
        Arrays.sort(s);
        int c = 0, 
        minLen=(int)Math.min(s[0].length(),
                s[s.length-1].length());
        while(c < minLen){
            if(s[0].charAt(c) == s[s.length-1].charAt(c))
                c++;
            else 
                break;
        }
        return s[0].substring(0, c);
    }
}

class Solution:
    def longestCommonPrefix(self, s: List[str]) -> str:
        s=sorted(s)
        c=0
        minLen=min(len(s[0]),len(s[-1]))
        while c<minLen :
            if s[0][c]==s[-1][c] :
                c+=1
            else :
                break
        return s[0][:c]