AlgoUniversity
  • Go Back
Discussion
Jewellery Designer :

Author

Dolton Fernandes

Difficulty Level : Hard

Submissions : 307

Asked In : Goldman-Sachs

Marks :10

: 2 | : 0

Natalie is a famous jewellery designer, known for her pearl necklace designs. She has a team that helps her create unique designs made of different types of pearls. The team creates individual string of pearls, and Natalie then arranges the strings in a beautiful way to make necklace. To begin with, Natalie prepares a rough sketch of the necklace by using a single character code to represent every pearl type she uses. The necklace design therefore looks like a series of strings in N different lines. Natalie's secret to making beautiful design to follow one specific rule. The rule is that two pearl strings can be consecutively arranged only if the two strings have a similar suffix chain such that length of the similar suffix chain is atmost one less than the length of the longer string i.e. two strings A and B are consecutively arranged only if LSC(A,B) >= max(|A|,|B|)-1 , where |A| indicates the length of string A.

Input

An integer $$$N$$$ $$$(1 \le N \le 10^6)$$$ denoting the number of strings in the input. Following $$$N$$$ lines contains one string $$$s_i$$$ $$$(1 \le |s_i| \le 10^6)$$$ per line.

Output

One integer denoting the size of the longest possible sequence of strings.

Examples

Input
4
gbpy
sbpy
bpy
bmy
Output
3
Input
5
rgb
ygb
mrwfna
gb
b
Output
4

Note

The sum of $$$|s_i|$$$ $$$(1 \le i \le N)$$$ doesn't exceed $$$10^6$$$.

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.