Longest Common Prefix (With Solution)

Longest Common Prefix

Problem Statement

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

Longest common prefix (LCP) 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”.

Prefix of abc

Examples:

Input: S[] = {“abcdefgh”, “abcefgh”}
Output: “abc”
Explanation: Explained in the image description above

Input: S[] = {“abcdefgh”, “aefghijk”, “abcefgh”}
Output: “a”


Horizontal Scanning Approach

The idea is to horizontally scan all the characters of the array of strings one by one and find the Longest Common Prefix among them. The LCP can be obtained as follows – 

LCP(S1…SN) = LCP(LCP(LCP(S1, S2), S3),…., SN)

Horizantal Scanning Approach
Horizontal Scanning Approach

Algorithm

  • Iterate through the string one by one from S1 till SN.
  • For each iteration till ith index, the LCP(S1…Si) can be obtained.
  • In case, the LCP is an empty string, terminate loop and return the empty string.
  • Else, continue and after scanning of N strings, the LCP(S1…SN) can be obtained.

C++ Implementation Horizontal Scanning

string longestCommonPrefix(vector<string>& S) {
        if (S.size() == 0) return "";
        std::string prefix = S[0];
 
        for (int i = 1; i < S.size(); ++i) {
          std::string s = S[i];
          if (s.size() == 0 || prefix == "") return "";
          prefix = prefix.substr(0, std::min(prefix.size(), s.size()) );
            
            for (int k = 0; k < s.size() && k < prefix.size(); ++k) {
                if (s[k] != prefix[k]) {
                    prefix = prefix.substr(0, k);
                    break;
                }
            }
        }
        return prefix;
    }

Java Implementation Horizontal Scanning

 public String longestCommonPrefix(String[] S) {
    if (S.length == 0) return "";
    String prefix = S[0];
    for (int i = 1; i < S.length; i++)
        while (S[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

Python Implementation Horizontal Scanning

def longestCommonPrefix(self, S):
    if "" in S or S == []:
        return ""
    preix = S[0]
    for i in range(1,len(S)):
        while(preix != ""):
            try:
                if str.index(str(S[i]),preix) == 0:
                    break
                else:
                    preix = preix[:-1]
            except:
                
                preix = preix[:-1]
    return preix

Time Complexity: O(N) where N is the size of the array S[].
Space Complexity: O(1), as no extra space is used.


Vertical Scanning Approach

The idea is to scan and compare the characters from top to bottom of the ith index for each string.

This approach is efficient in cases when the LCP string is very small. Hence, we do not need to perform K comparisons.

LCP Vertical Scanning Approach
Vertical Scanning Approach

Algorithm

  • Iterate through the string one by one from S1 till SN.
  • Start comparing the 0th index, 1st index … ith index simultaneously for each string.
  • In case, any of the ith index characters doesn’t match, terminate the algorithm and return the LPS(1,i)
  • Else, continue and after scanning of N strings, the LCP(S1…SN) can be obtained.

C++ Implementation of Vertical Scanning

string longestCommonPrefix(vector<string> S) {
    if (S.size() == 0) return "";
    for (int i = 0; i < S[0].length() ; i++){
        char c = S[0][i];
        for (int j = 1; j < S.length; j ++) {
            if (i == S[j].length() || S[j][i] != c)
                return S[0].substr(0, i);             
        }
    }
    return S[0];
}

Java Implementation of Vertical Scanning

public String longestCommonPrefix(String[] S) {
    if (S == null || S.length == 0) return "";
    for (int i = 0; i < S[0].length() ; i++){
        char c = S[0].charAt(i);
        for (int j = 1; j < S.length; j ++) {
            if (i == S[j].length() || S[j].charAt(i) != c)
                return S[0].substring(0, i);             
        }
    }
    return S[0];
}

Python Implementation of Vertical Scanning

def longestCommonPrefix(S) {
    if (len(S) == 0) return "";
    for i in range(len(S[0])):
        c = S[0][i];
        for j in range(len(S)):
            if i == len(S[j]) or  S[j][i] != c)
                return S[0][0:i];             
        }
    }
    return S[0];
}

Time Complexity: O(K) where K is the sum of all the characters in all strings.
Space Complexity: O(1), as no extra space is used.


Divide and Conquer Approach

The approach is to divide the given array of strings into various subproblems and merge them to get the LCP(S1..SN).

First, divide the given array into two parts. Then, in turn, divide the left and right array obtained into two parts and recursively keep dividing them, until they cannot be divided further.

Mathematically,LCP(S1….SN) = LCP(S1….Sk) + LCP(Sk+1…SN), where LCP(S1..SN) is the LCP of the array of strings and 1 < k < N.

LCP Divide and Conquer Approach
Divide and Conquer Approach

Algorithm:

  • Recursively divide the input array of strings into two parts.
  • For each division, find the LCP obtained so far.
  • Merge the obtained LCP from both the subarrays and return it.
  • I.e. LCP(LCP(S[left…mid], LCP(S[mid + 1, right])) and return it.

C++ Implementation

string commonPrefixUtil(string str1, string str2)
{
    string result;
    int n1 = str1.length(), n2 = str2.length();
 
    for (int i=0, j=0; i<=n1-1&&j<=n2-1; i++,j++)
    {
        if (str1[i] != str2[j])
            break;
        result.push_back(str1[i]);
    }
    return (result);
}
string longestCommonPrefix(string S[], int low, int high)
{
    if (low == high)
        return (S[low]);
 
    if (high > low)
    {
        int mid = low + (high - low) / 2;
 
        string str1 = commonPrefix(S, low, mid);
        string str2 = commonPrefix(S, mid+1, high);
 
        return (commonPrefixUtil(str1, str2));
    }
}

Java Implementation

static String commonPrefixUtil(String str1, String str2) {
        String result = "";
        int n1 = str1.length(), n2 = str2.length();
 
        for (int i = 0, j = 0; i <= n1 - 1 &&
                j <= n2 - 1; i++, j++) {
            if (str1.charAt(i) != str2.charAt(j)) {
                break;
            }
            result += str1.charAt(i);
        }
        return (result);
    }
    static String longestCommonPrefix(String S[], int low, int high) {
        if (low == high) {
            return (S[low]);
        }
 
        if (high > low) {
            int mid = low + (high - low) / 2;
 
            String str1 = commonPrefix(S, low, mid);
            String str2 = commonPrefix(S, mid + 1, high);
 
            return (commonPrefixUtil(str1, str2));
        }
        return null;
    }

Python Implementation

def commonPrefixUtil(str1, str2):
 
    result = ""
    n1, n2 = len(str1), len(str2)
    i, j = 0, 0
 
    while i <= n1 - 1 and j <= n2 - 1:
     
        if str1[i] != str2[j]:
            break
        result += str1[i]
        i, j = i + 1, j + 1
     
    return result
 
 
def longestCommonPrefix(S, low, high):
 
    if low == high:
        return S[low]
 
    if high > low:
        mid = low + (high - low) // 2
 
        str1 = commonPrefix(S, low, mid)
        str2 = commonPrefix(S, mid + 1, high)
 
        return commonPrefixUtil(str1, str2)

Time Complexity: O(K) where K is the sum of all the characters in all strings.
Space Complexity: O(M log N), as there are log N recursive calls and each needs a space of M.

Binary Search Approach

Another way to approach the problem is to use the concept of Binary Search.

Algorithm:

  • Consider the string with the smallest length. Let the length be L.
  • Consider a variable low = 0 and high =  L – 1.
  • Perform binary search:
    • Divide the string into two halves, i.e. low – mid and mid + 1 to high.
    • Compare the substring upto the mid of this smallest string to every other character of the remaining strings at that index.
    • If the substring from 0 to mid – 1 is common among all the substrings, update low with mid + 1, else update high with mid – 1
    • If low == high, terminate the algorithm and return the substring from 0 to mid.

C++ Implementation of Binary Search Approach

int findMinLength(string S[], int n)
{
    int min = INT_MAX;
  
    for (int i=0; i<=n-1; i++)
        if (S[i].length() < min)
            min = S[i].length();
    return(min);
}
  
bool allContainsPrefix(string S[], int n, string str,
                       int start, int end)
{
    for (int i=0; i<=n-1; i++)
        for (int j=start; j<=end; j++)
            if (S[i][j] != str[j])
                return (false);
    return (true);
}
string longestCommonPrefix(string S[], int n)
{
    int index = findMinLength(S, n);
    string prefix; 
    int low = 0, high = index;
  
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
  
        if (allContainsPrefix (S, n, S[0], low, mid))
        {
            prefix = prefix + S[0].substr(low, mid-low+1);
            low = mid + 1;
        }
  
        else 
            high = mid - 1;
    }
  
    return (prefix);
}

Java Implementation of Binary Search Approach

static int findMinLength(String S[], int n)
    {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <= (n - 1); i++) 
        {
            if (S[i].length() < min) {
                min = S[i].length();
            }
        }
        return min;
    }
  
    static boolean allContainsPrefix(String S[], int n, 
                         String str, int start, int end)
    {
        for (int i = 0; i <= (n - 1); i++)
        {
            String S_i = S[i];
              
            for (int j = start; j <= end; j++)
                if (S_i.charAt(j) != str.charAt(j))
                    return false;
        }
        return true;
    }
  
    static String longestCommonPrefix(String S[], int n)
    {
        int index = findMinLength(S, n);
        String prefix = ""; 
        int low = 0, high = index-1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
  
            if (allContainsPrefix(S, n, S[0], low,
                                                  mid))
            {
                prefix = prefix + S[0].substring(low, mid + 1);
                low = mid + 1;
            } 
            else 
            {
                high = mid - 1;
            }
        }
  
        return prefix;
    }

Python Implementation of Binary Search Approach

def findMinLength(strList):
    return len(min(S, key = len))
  
def allContainsPrefix(strList, str, 
                      start, end):
    for i in range(0, len(strList)):
        word = strList[i]
        for j in range(start, end + 1):
            if word[j] != str[j]:
                return False
    return True
  
def longestCommonPrefix(strList):
    index = findMinLength(strList)
    prefix = ""   
  
    low, high = 0, index - 1
    while low <= high:
        mid = int(low + (high - low) / 2)
        if allContainsPrefix(strList,   
                             strList[0], low, mid):
              
            prefix = prefix + strList[0][low:mid + 1]
  
            low = mid + 1
        else: 
            high = mid - 1
  
    return prefix

Time Complexity: O(K. logN) where K is the sum of all the characters in all strings.
Space Complexity: O(1)


Practice Question

Longest Common Prefix


Frequently Asked Questions

What is the best time and space complexity of finding the longest prefix string?
The best time complexity is O(N) and the space complexity is O(1) using the horizontal and vertical scanning approach.

Is the binary search approach better than the other approaches?
No, the binary search takes O(K*logN) time complexity. Hence, it is not the most efficient approach.

Previous Post
Longest Common Substring

Longest Common Substring

Next Post
Rearrange Array Alternately

Rearrange Array Alternately

Crack your next tech interview with confidence!
Take a free mock interview, get instant⚡️ feedback and recommendation💡
Take Free Mock Interview
Total
0
Share