Longest Common Prefix

Problem Statement

Given an array of strings, find the longest common prefix (LCP) among all strings in the array. The longest common prefix of a set of strings is the longest string that is a prefix of all strings in the set.

Examples

Example 1

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

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

Example 2

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

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

Example 3

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

Constraints

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

Approaches

1️⃣ Naive Approach

Intuition:

The idea behind this code is to find the longest common prefix among all strings in the vector by comparing characters at each position one by one across all strings.

1. Character by Character Comparison: Start by comparing the first character of all strings, then move to the second character, and so on.
2. Break on Mismatch: If at any position, any string does not have the same character, then stop checking further, as no further common prefix exists beyond that point.
3. Collect Common Characters: If all strings have the same character at a given position, add that character to the result string

Steps to Solve the Problem

1. Check for Empty Input: If the vector of strings is empty, return an empty string because there are no strings to compare.
2. Initialize the Common Prefix: Start with an empty string commonPrefix to store the resulting longest common prefix.
3. Use the First String as Reference: Since the common prefix can’t be longer than the shortest string, start with the first string as the reference for comparisons.
4. Iterate Through Each Character of the First String:
   • For each character in the first string:
     • Assume it is part of the common prefix.
     • Check this character at the same position in all other strings.
     • If any string does not match, stop and return the current common prefix.
5. Update the Common Prefix: If the character matches in all strings, append it to commonPrefix.
6. Terminate on Mismatch: Break out of the loop and return the common prefix when a mismatch is found.

Code:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestCommonPrefix(vector<string>& str) {
    if (str.empty()) return ""; // Return empty string if no strings are present

    string commonPrefix = "";  // Initialize the result to an empty string
    string firstStr = str[0];  // Use the first string as the reference
    int size = firstStr.size();  // Get the length of the first string

    // Iterate through each character of the first string
    for (int i = 0; i < size; i++) {
        char alphabet = firstStr[i];  // Current character to match
        bool common = true;  // Assume it is common until proven otherwise

        // Compare this character with all strings in the vector
        for (string strr : str) {
            // Check if the current string is long enough and characters match
            if (i >= strr.size() || strr[i] != alphabet) {
                common = false;  // Found a mismatch or string is too short
                break;  // Exit the loop if a mismatch is found
            }
        }

        if (common) {
            commonPrefix += alphabet;  // Append matching character to the prefix
        } else {
            break;  // Stop if any mismatch is found
        }
    }

    return commonPrefix;  // Return the final common prefix
}

int main() {
    vector<string> strs1 = {"flower", "flow", "flight"};
    cout << "Longest Common Prefix: " << longestCommonPrefix(strs1) << endl;  // Output: "fl"

    vector<string> strs2 = {"dog", "racecar", "car"};
    cout << "Longest Common Prefix: " << longestCommonPrefix(strs2) << endl;  // Output: ""

    return 0;
}

Complexity Analysis:

• Time Complexity: O(S)O(S)O(S) , where SSS is the total number of characters in all strings.
  • Explanation:
    • The outer loop runs for each character in the first string, and the inner loop checks this character against all other strings.
    • In the worst case, all strings are the same and we compare every character in every string.
    • The total number of comparisons is proportional to the sum of all characters across all strings.
• Space Complexity: O(1)O(1)O(1) .
  • Explanation:
    • The algorithm uses a fixed amount of extra space (variables commonPrefix, firstStr, i, alphabet, and common).
    • No additional space is used that grows with the input size, hence it is constant.

2️⃣ Vertical Scanning:

This is the enhanced form of the Naive approach.

In this approach, we start by comparing the characters of each string in a vertical manner, column by column. If a mismatch is found, we stop and return the prefix found so far.

#include <iostream>
#include <vector>
#include <string>

std::string longestCommonPrefix(std::vector<std::string>& strs) {
    if (strs.empty()) return "";

    for (int i = 0; i < strs[0].size(); ++i) {
        char c = strs[0][i];
        for (int j = 1; j < strs.size(); ++j) {
            if (i == strs[j].size() || strs[j][i] != c) {
                return strs[0].substr(0, i);
            }
        }
    }
    return strs[0];
}

int main() {
    std::vector<std::string> strs = {"flower", "flow", "flight"};
    std::cout << "Longest Common Prefix: " << longestCommonPrefix(strs) << std::endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(S) where S is the sum of all characters in all strings. In the worst case, all strings are the same.
• Space Complexity: O(1) since no additional data structures are used.

3️⃣ Horizontal Scanning

Here, we take the first string as the prefix and then compare it with each subsequent string. We gradually reduce the prefix until it matches all strings.

#include <iostream>
#include <vector>
#include <string>

std::string longestCommonPrefix(std::vector<std::string>& strs) {
    if (strs.empty()) return "";
    
    std::string prefix = strs[0];
    for (int i = 1; i < strs.size(); ++i) {
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

int main() {
    std::vector<std::string> strs = {"flower", "flow", "flight"};
    std::cout << "Longest Common Prefix: " << longestCommonPrefix(strs) << std::endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(S), where S is the sum of all characters in all strings. The algorithm still has to scan all characters in the worst case.
• Space Complexity: O(1), since the prefix is the only additional storage used.