{ }

Initializing AlgoBuddy...

Optimizing your workspace

Longest Common Prefix

Enter strings (comma separated)

Longest Common Prefix

"fl"

Length: 2

What is Longest Common Prefix?

The Longest Common Prefix (LCP) of a group of strings is the longest prefix shared by every string. If no common prefix exists, the result is an empty string.

This problem frequently appears in coding interviews and is useful in autocomplete systems, dictionaries, search engines, and text processing.

Example

Input:

["flower", "flow", "flight"]

Output:

"fl"

Algorithm

Take the first string as the initial prefix.
Compare it with every remaining string.
If the current string doesn't start with the prefix, remove the last character from the prefix.
Repeat until every string begins with the prefix.
Return the final prefix.

Complexity Analysis

Best Case: O(n)
Average Case: O(n × m)
Worst Case: O(n × m)
Space Complexity: O(1)

Time Complexity Analysis

C++

#include <iostream>
#include <vector>
using namespace std;

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

    string prefix = strs[0];

    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix.pop_back();

            if (prefix.empty())
                return "";
        }
    }

    return prefix;
}

int main() {
    vector<string> strs = {"flower", "flow", "flight"};

    cout << "Longest Common Prefix: "
         << longestCommonPrefix(strs);

    return 0;
}

Java

class Solution {

    public String longestCommonPrefix(String[] strs) {

        if (strs.length == 0) return "";

        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {

            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);

                if (prefix.isEmpty())
                    return "";
            }
        }

        return prefix;
    }
}

Python

def longest_common_prefix(strs):

    if not strs:
        return ""

    prefix = strs[0]

    for word in strs[1:]:

        while not word.startswith(prefix):
            prefix = prefix[:-1]

            if prefix == "":
                return ""

    return prefix

print(longest_common_prefix(
    ["flower","flow","flight"]
))

JavaScript

function longestCommonPrefix(strs) {

    if (strs.length === 0) return "";

    let prefix = strs[0];

    for (let i = 1; i < strs.length; i++) {

        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.slice(0, -1);

            if (prefix === "")
                return "";
        }
    }

    return prefix;
}

console.log(
    longestCommonPrefix([
        "flower",
        "flow",
        "flight"
    ])
);

Explore other string algorithms

Reverse String

Palindrome Check

Character Frequency

Anagram Check

Longest Common Prefix

Enter strings (comma separated)

Longest Common Prefix

"fl"

Length: 2

What is Longest Common Prefix?

The Longest Common Prefix (LCP) of a group of strings is the longest prefix shared by every string. If no common prefix exists, the result is an empty string.

This problem frequently appears in coding interviews and is useful in autocomplete systems, dictionaries, search engines, and text processing.

Example

Input:

["flower", "flow", "flight"]

Output:

"fl"

Algorithm

Take the first string as the initial prefix.
Compare it with every remaining string.
If the current string doesn't start with the prefix, remove the last character from the prefix.
Repeat until every string begins with the prefix.
Return the final prefix.

Complexity Analysis

Best Case: O(n)
Average Case: O(n × m)
Worst Case: O(n × m)
Space Complexity: O(1)

Time Complexity Analysis

C++

#include <iostream>
#include <vector>
using namespace std;

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

    string prefix = strs[0];

    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix.pop_back();

            if (prefix.empty())
                return "";
        }
    }

    return prefix;
}

int main() {
    vector<string> strs = {"flower", "flow", "flight"};

    cout << "Longest Common Prefix: "
         << longestCommonPrefix(strs);

    return 0;
}

Java

class Solution {

    public String longestCommonPrefix(String[] strs) {

        if (strs.length == 0) return "";

        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {

            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);

                if (prefix.isEmpty())
                    return "";
            }
        }

        return prefix;
    }
}

Python

def longest_common_prefix(strs):

    if not strs:
        return ""

    prefix = strs[0]

    for word in strs[1:]:

        while not word.startswith(prefix):
            prefix = prefix[:-1]

            if prefix == "":
                return ""

    return prefix

print(longest_common_prefix(
    ["flower","flow","flight"]
))

JavaScript

function longestCommonPrefix(strs) {

    if (strs.length === 0) return "";

    let prefix = strs[0];

    for (let i = 1; i < strs.length; i++) {

        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.slice(0, -1);

            if (prefix === "")
                return "";
        }
    }

    return prefix;
}

console.log(
    longestCommonPrefix([
        "flower",
        "flow",
        "flight"
    ])
);

Explore other string algorithms

Reverse String

Palindrome Check

Character Frequency

Anagram Check