Longest common prefix (Character by character)

In the given input set of strings, write a program to find the longest common prefix.


Input strings : {“code”, ”codex”, ”cosec”, ”coding”,”cobalt”}
Output : “co”

Time complexity : O(NM),

N = Number of strings
M = Length of longest string

Space complexity : O(M)


Here, instead of going through strings one by one, we will go through characters one by one.

1. We find the minimum length string from the input string array.
a. Traverse the string array.
   b. Return length of minimum length string.

2. We traverse all the strings, and compare characters at same position.

3. If current character is same in all strings (same position) add it to result.

4. Return final result.

C++ Program

#include <bits/stdc++.h>

using namespace std;
//Function to find
//Length of minimum length string
int findMinLength(string string_array[], int n)
    int min = string_array[0].length();
    for (int i=1; i<n; i++)
        if (string_array[i].length() < min)
            min = string_array[i].length();
string LCP(string string_array[], int n)
    int minlen = findMinLength(string_array, n);
    string output; //output string
    char curr_char;
    for (int i=0; i<minlen; i++)
        //Compare all characters at same position in all strings 
        //If true append
        curr_char = string_array[0][i];
        for (int j=1 ; j<n; j++)
            if (string_array[j][i] != curr_char)
                return output;
        //Append to output
    return (output);
//Main function
int main()
    string string_array[] = {"code","codex", "cosec", "coding","cobalt"};
    int length = sizeof(string_array)/sizeof(string_array[0]);
    string ans = LCP(string_array, length);
        cout<<"Longest common prefix is: "<<ans;
        cout<<"No common prefix found";
    return 0;

Try It


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions