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.
Ex:
A: "gbpy"
B: "sbpy"
C:"bpy"
D:"bmy"
LSC(A,B)=max(|4|,|4|)-1=3
In this example atleast 3 suffix codes should exactly be same in A and B.
Her Team has brought in today's pearl strings, and Natalie is arranging them consecutively in necklace. She wants to create as big a necklace as possible. Write a program to help her arrange the longest possible sequence of strings, such that each two consecutive strings follow the rule.
Input:
4
gbpy
sbpy
bpy
bmy
Output:
3
Explanation:
Number of strings=4
Consider first 2 strings "gbpy" and "sbpy", they have 3 similar pearls in the suffix chain "bpy" hence LSC=3
Max(|4|,|4|)-1=4-1=3
Hence these 2 strings can be consecutively arranged.
Similarly both "gbpy" and "sbpy" can be arranged with "bpy" also. However the string "bmy" does not have a suffix chain similar enough with any other string to follow the rule.
Hence the longest possible arrangement is with 3 strings and the O/P is therefore 3.
Input 2:
5
rgb
ygb
mrwfna
gb
b
O/P:
4
The longest possible arrangement is with 4 strings
rgb
ygb
gb
b.
Please help me in solving this question.
If there is similar que related to it, comment it down below.