This page is still under construction.

Parts of this page are still being built. What you see may change.

Longest Common Substring

Interview

Time limit1sMemory limit1024 MB

Summary
Given up to 1000 lowercase strings of length at most 100, find the length of the longest substring that appears in every string.
Level

Medium6 of 10

Topics
String, Dynamic programming, Binary search, Hash map
Solved
No attempts yet

Problem

Given a list of strings, what is the longest substring common to all of them?

Input

The first line of input contains an integer nn (1≤n≤1,0001 \le n \le 1,000), which is the number of strings that follow.

Each of the next nn lines contains a single string ss (1≤∣s∣≤1001 \le |s| \le 100) consisting only of lower-case letters.

Output

Output a single integer, which is the length of the longest substring common to all of the input strings.

Examples1

  1. Example 1

    Input
    5
axabcrwmvd
abcn
tabchwqsl
bvrkabcayna
tyabc
    Expected output
    3