Longest common prefix

Beginner Problems Basic Strings Easy

Fun Fact: The problem of finding the longest common prefix among an array of strings is often used in the field of autocompletion and suggestion engines, which are quite prevalent in search engines, IDEs (Integrated Development Environments), and so on
When a user starts typing something, these engines use the longest common prefix algorithm to generate relevant and instant suggestions to the user based on historical and contextual data
Such functionalities optimize the user experience and efficiency in using the software application

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 "".

Examples:

Input : str = ["flowers" , "flow" , "fly", "flight" ]

Output : "fl"

Explanation : All strings given in array contains common prefix "fl".

Input : str = ["dog" , "cat" , "animal", "monkey" ]

Output : ""

Explanation : There is no common prefix among the given strings in array.

Input : str = ["lady" , "lazy"]

Constraints

1 <= str.length <= 200
1 <= str[i].length <= 200
str[i] contains only lowercase English letters.

Company Tags

TCS Cognizant Accenture Infosys Capgemini Wipro IBM HCL Tech Mahindra MindTree

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/7QXqt6Y62c9/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition

To determine the longest common prefix among a set of strings, consider the following approach: when a list of strings is sorted lexicographically, the first string and the last string in this sorted list will have the longest common prefix. This is because, in a sorted list, the closest strings in terms of lexicographical order are adjacent, making their common prefix the longest possible for the entire list. For example, if the sorted list is ["apple", "applet", "banana"], comparing the first and last string in the sorted order gives the common prefix shared by all strings in the list.

Approach

Sort the array of strings.
Select the first and the last string from the sorted array. These two strings will have the maximum possible common prefix.
Initialize an index variable to zero. This index will track the length of the common prefix.
Compare characters at the current index of both selected strings. Continue moving the index forward as long as the characters at the current index are equal and the index is within the bounds of both strings.
Once characters differ or the end of one of the strings is reached, the index will indicate the length of the common prefix.
Return the substring of the first string from the start to the index, which represents the longest common prefix.

Dry Run

Solution

#include<bits/stdc++.h>
using namespace std;


class Solution {
public:
    // Method to find the longest common prefix in a vector of strings
    string longestCommonPrefix(vector<string>& str) {
        // Edge case: empty vector
        if (str.empty()) return "";
        
        // Sort the vector to get the lexicographically smallest and largest strings
        sort(str.begin(), str.end());
        // First string (smallest in sorted order)
        string first = str[0]; 
        // Last string (largest in sorted order)
        string last = str[str.size() - 1]; 
        
        // Compare characters of the first and last strings
        int minLength = min(first.size(), last.size());
        string ans = "";
        for (int i = 0; i < minLength; i++) {
            // If characters don't match, return the current prefix
            if (first[i] != last[i]) {
                return ans;
            }
            // Append the matching character to the result
            ans += first[i];
        }
        
        // Return the longest common prefix found
        return ans;
    }
};

// Main function to test the longestCommonPrefix method
int main() {
    Solution solution;
    vector<string> input = {"flower", "flow", "flight"};
    string result = solution.longestCommonPrefix(input);
    cout << "Longest Common Prefix: " << result << endl; // Output: "fl"
    return 0;
}
import java.util.Arrays;

class Solution {
    // Method to find the longest common prefix in an array of strings
    public String longestCommonPrefix(String[] v) {
        // Use StringBuilder to build the result
        StringBuilder ans = new StringBuilder();
        
        // Sort the array to get the lexicographically smallest and largest strings
        Arrays.sort(v);
        // First string (smallest in sorted order)
        String first = v[0]; 
         // Last string (largest in sorted order)
        String last = v[v.length - 1];
        
        // Compare characters of the first and last strings
        for (int i = 0; i < Math.min(first.length(), last.length()); i++) {
            // If characters don't match, return the current prefix
            if (first.charAt(i) != last.charAt(i)) {
                return ans.toString();
            }
            // Append the matching character to the result
            ans.append(first.charAt(i));
        }
        
        // Return the longest common prefix found
        return ans.toString();
    }
    
    // Main method to test the longestCommonPrefix method
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] input = {"flower", "flow", "flight"};
        String result = solution.longestCommonPrefix(input);
        System.out.println("Longest Common Prefix: " + result); // Output: "fl"
    }
}
class Solution:
    # Method to find the longest common prefix in a list of strings
    def longestCommonPrefix(self, strs):
        # Edge case: empty list
        if not strs:
            return ""
        
        # Sort the list to get the lexicographically smallest and largest strings
        strs.sort()
        # First string (smallest in sorted order)
        first = strs[0]  
        # Last string (largest in sorted order)
        last = strs[-1]  
        
        # Compare characters of the first and last strings
        ans = []
        for i in range(min(len(first), len(last))):
            # If characters don't match, return the current prefix
            if first[i] != last[i]:
                return ''.join(ans)
            # Append the matching character to the result
            ans.append(first[i])
        
        # Return the longest common prefix found
        return ''.join(ans)

# Test the longestCommonPrefix method
if __name__ == "__main__":
    solution = Solution()
    input_strs = ["flower", "flow", "flight"]
    result = solution.longestCommonPrefix(input_strs)
    print("Longest Common Prefix:", result)  # Output: "fl"
class Solution {
    // Method to find the longest common prefix in an array of strings
    longestCommonPrefix(strs) {
        // Edge case: empty array
        if (strs.length === 0) return "";

        // Sort the array to get the lexicographically smallest and largest strings
        strs.sort();
        // First string (smallest in sorted order)
        const first = strs[0]; 
        // Last string (largest in sorted order)
        const last = strs[strs.length - 1]; 
        
        let commonPrefix = "";
        
        // Compare characters of the first and last strings
        for (let i = 0; i < Math.min(first.length, last.length); i++) {
            // If characters don't match, return the current prefix
            if (first[i] !== last[i]) {
                return commonPrefix;
            }
            // Append the matching character to the result
            commonPrefix += first[i];
        }
        
        // Return the longest common prefix found
        return commonPrefix;
    }
}

// Test the longestCommonPrefix method
const solution = new Solution();
const inputStrs = ["flower", "flow", "flight"];
const result = solution.longestCommonPrefix(inputStrs);
console.log("Longest Common Prefix:", result); // Output: "fl"

Complexity Analysis

Time Complexity: O(N * log N + M), where N is the number of strings and M is the minimum length of a string. The sorting operation takes O(N * log N) time, and the comparison of characters in the first and last strings takes O(M) time.

Space Complexity: O(M), as the ans variable can store the length of the prefix which in the worst case will be O(M).

Code

Problem List