Longest Common Prefix InterviewBit Solution

Problem: Longest Common Prefix

Problem Description:

Given the array of strings A, you need to find the longest string S which is the prefix of ALL the strings in the array.

Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2.

For Example, longest common prefix of "abcdefgh" and "abcefgh" is "abc".

Input Format

The only argument given is an array of strings A. 

Output Format

Return longest common prefix of all strings in A. 

Example:

Input 1:
    A = ["abcdefgh", "aefghijk", "abcefgh"]
Output 1:
    "a"
    Explanation 1:
        Longest common prefix of all the strings is "a".

Input 2:
    A = ["abab", "ab", "abcd"];
Output 2:
    "ab"
    Explanation 2:
        Longest common prefix of all the strings is "ab"

Approach:

A simple brute force approach is to take any one string and traverse it from start to end and for each index traverse all the string present in the array.

For example:
    A = ["abab", "ab", "abcd"];
    Take string "abab" for example and start with its first index.
    Index = 0, 
        A[0][0] = A[1][0] = A[2][0] = 'a',    ans = "a"
        
    Index = 1,
        A[0][1] = A[1][1] = A[2][1] = 'b',    ans = "ab"
        
    Index = 2, 
        A[0][2] != A[1][2], so break and ans will remain "ab".

For the above approach time complexity would be O(N*M), where N is the size of string array, and M is the size of the smallest string.

Another approach would be to sort the string array, and then compare the first and last strings, as these string are the strings that are most different to each other.

Time & Space Complexity:

Method 1:

Time Complexity: 
    - O(N * M) where,
         N is the size of String Array and
         M is the size of smallest string

Space Complexity:
    - O(N*M) 
        To store the String Array.

Method 2:

Time Complexity: 
     Since we are sorting the string array and sorting takes O(NLogN), but in sorting we compare elements too, and here element is string, so to compare strings take O(M) time. Therefore, time complexity for this approach would be 
    - O(N * M * LogN) where,
         N is the size of String Array and
         M is the size of smallest string

Space Complexity:
    - O(N*M) 
        To store the String Array.
        

Solution:

Method 1: Code in C++

Method 2: Code in C++