5. Longest Common Prefix

Difficulty: easy · String

Problem

Given `n` words, find the **longest common prefix** shared by all of them. If they share no prefix at all, print `NONE`.

Input

The first line holds `n`. Each of the next `n` lines holds one word.

Output

Print the longest common prefix, or `NONE`.

Example 1

Input:
3
flower
flow
flight
Output:
fl

Explanation: Every word starts with "fl", and no longer prefix is shared by all of them.

Example 2

Input:
3
dog
racecar
car
Output:
NONE

Explanation: The words do not all start with the same letter, so there is no common prefix.

Example 3

Input:
1
alone
Output:
alone

Explanation: Every word starts with "alone", and no longer prefix is shared by all of them.

Example 4

Input:
2
prefix
prefix
Output:
prefix

Explanation: Every word starts with "prefix", and no longer prefix is shared by all of them.

Example 5

Input:
4
interspecies
interstellar
interstate
internet
Output:
inter

Explanation: Every word starts with "inter", and no longer prefix is shared by all of them.

Example 6

Input:
3
ab
a
abc
Output:
a

Explanation: Every word starts with "a", and no longer prefix is shared by all of them.

Example 7

Input:
2
class
glass
Output:
NONE

Explanation: The words do not all start with the same letter, so there is no common prefix.

Example 8

Input:
3
throne
throw
through
Output:
thro

Explanation: Every word starts with "thro", and no longer prefix is shared by all of them.

Example 9

Input:
5
code
coder
coding
codec
codex
Output:
cod

Explanation: Every word starts with "cod", and no longer prefix is shared by all of them.

Example 10

Input:
2
x
y
Output:
NONE

Explanation: The words do not all start with the same letter, so there is no common prefix.

Constraints

- 1 <= n <= 200 - 1 <= word length <= 1000 - Words consist of lowercase English letters.

Solutions are judged against 10 sample and 5 hidden tests. Sign in to solve it · All problems