Substring of a Substring Codechef Solution | MARCH CHALLENGE
Substring of a Substring CodeChef Solution:
Shefin gives you a string SS and you have to find a non-empty string PP such that:
- PP is a substring of SS.
- No non-empty substring of PP is a prefix of SS.
- No non-empty substring of PP is a suffix of SS.
For all such possible strings, find the length of the longest string satisfying all the conditions. If no such string is possible, print −1−1.
A string AA is a substring of a string BB if AA can be obtained from BB by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end.
A prefix of a string AA, is a substring of AA that occurs at the beginning of AA. For example, “code” is a prefix of “codechef”, but “ode” is not.
A suffix of a string AA, is a substring of AA that occurs at the end of AA. For example, “chef” is a suffix of “codechef”, but “he” is not.
Input Format
- The first line of the input contains an integer TT — denoting number of test cases.
- Each test case contains a string SS consisting of lowercase english alphabets only.
Output Format
For each test case, print a single integer. If a string PP exists based on the given conditions, print the maximum length of the possible string. Otherwise, print −1−1.
Constraints
- 1≤T≤1041≤T≤104
- 1≤|S|≤1061≤|S|≤106
- Sum of |S||S| over all test cases does not exceed 106106.
- SS consists of lowercase english alphabets only.
Sample Input 1
2
abcdab
aaa
Sample Output 1
2
-1
Explanation
Test Case 11: The maximum length of the string satisfying all required conditions is 22. The string cdcd satisfies all the conditions. It can be proven that no string of length greater than 22 exists which can satisfy all the conditions.
Test Case 22: There is no string possible which satisfies all the required conditions. Thus, the answer is −1−1.
Substring of a Substring SOLUTION
C++
Join our telegram group for codes.
Java
Will be Updated soon
Python
Will be Updated soon
Read More Post Here
