#include <string>
#include <vector>
using namespace std;
 
string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
 
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0][i];
        for (int j = 1; j < strs.size(); j++) {
            // If we've reached the end of any string or chars disagree
            if (i >= strs[j].length() || strs[j][i] != c) {
                return strs[0].substr(0, i);
            }
        }
    }
    return strs[0];  // First string is the prefix of all others
}

def longest_common_prefix(strs):
    if not strs:
        return ""
 
    for i in range(len(strs[0])):
        char = strs[0][i]
        for j in range(1, len(strs)):
            if i >= len(strs[j]) or strs[j][i] != char:
                return strs[0][:i]
 
    return strs[0]
 
print(longest_common_prefix(["flower", "flow", "flight"]))  # "fl"
print(longest_common_prefix(["dog", "racecar", "car"]))     # ""

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

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
 
    sort(strs.begin(), strs.end());
 
    string first = strs[0];
    string last = strs[strs.size() - 1];
    int i = 0;
 
    while (i < first.length() && i < last.length() && first[i] == last[i]) {
        i++;
    }
    return first.substr(0, i);
}

def longest_common_prefix_sort(strs):
    if not strs:
        return ""
 
    strs.sort()
    first, last = strs[0], strs[-1]
    i = 0
 
    while i < len(first) and i < len(last) and first[i] == last[i]:
        i += 1
 
    return first[:i]
 
# Python one-liner using zip
def lcp_pythonic(strs):
    prefix = []
    for chars in zip(*strs):
        if len(set(chars)) == 1:
            prefix.append(chars[0])
        else:
            break
    return "".join(prefix)
 
print(lcp_pythonic(["flower", "flow", "flight"]))  # "fl"