Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Strings

Longest Common Prefix

Easy · Strings · Asked at Amazon, Google, Microsoft, TCS, Infosys

Find the longest common prefix of all the given words. Print -1 if there is no common prefix.

Input

First line: n. Second line: n words separated by spaces.

Output

The longest common prefix, or -1.

Constraints

Example 1

Input

3
flower flow flight

Output

fl

Example 2

Input

3
dog racecar car

Output

-1

Hints

  1. The answer can be no longer than the first word.
  2. Shorten a candidate prefix (start with the first word) until every other word starts with it.

Approach

Take the first word as the prefix. For each other word, compare character by character and cut the prefix at the first mismatch, or at the shorter length. If the prefix ever becomes empty there is no common prefix: print -1.

Complexity: O(total characters) time · O(1) extra space

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    vector<string> w(n);
    for (auto &x : w) cin >> x;
    string prefix = w[0];
    for (int i = 1; i < n; i++) {
        size_t k = 0;
        while (k < prefix.size() && k < w[i].size() && prefix[k] == w[i][k]) k++;
        prefix = prefix.substr(0, k);
    }
    cout << (prefix.empty() ? "-1" : prefix) << "\n";
    return 0;
}

Python solution

import os

n = int(input())
words = input().split()
prefix = os.path.commonprefix(words[:n])
print(prefix if prefix else -1)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String prefix = sc.next();
        for (int i = 1; i < n; i++) {
            String w = sc.next();
            int k = 0;
            while (k < prefix.length() && k < w.length() && prefix.charAt(k) == w.charAt(k)) k++;
            prefix = prefix.substring(0, k);
        }
        System.out.println(prefix.isEmpty() ? "-1" : prefix);
    }
}

Solve Longest Common Prefix online · All practice problems