# Substring of a Substring Solution Codechef

## Substring of a Substring Solution Codechef

Shefin gives you a string S and you have to find a non-empty string P such that:

• P is a substring of S.
• No non-empty substring of P is a prefix of S.
• No non-empty substring of P is a suffix of S.
• For all such possible strings, find the length of the longest string satisfying all the conditions. If no such string is possible, print −1.

A string A is a substring of a string B if A can be obtained from B by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end.
A prefix of a string A, is a substring of A that occurs at the beginning of A. For example, “code” is a prefix of “codechef”, but “ode” is not.
A suffix of a string A, is a substring of A that occurs at the end of A. For example, “chef” is a suffix of “codechef”, but “he” is not.

Input Format

• The first line of the input contains an integer T – denoting number of test cases.
• Each test case contains a string S consisting of lowercase English alphabets only.

Output Format

For each test case, print a single integer. If a string P exists based on the given conditions, print the maximum length of the possible string. Otherwise, print −1.

Constraints

• 1≤T≤10^4
• 1≤|S|≤10^6
• Sum of |S| over all test cases does not exceed 10^6.
• S consists of lowercase english alphabets only.

Sample Input 1

``````2
abcdab
aaa``````

Sample Output 1

``````2
-1``````

Explanation

• Test Case 1: The maximum length of the string satisfying all required conditions is 2. The string cd satisfies all the conditions. It can be proven that no string of length greater than 2 exists which can satisfy all the conditions.
• Test Case 2: There is no string possible which satisfies all the required conditions. Thus, the answer is −1.

### SOLUTION

Program: Substring of a Substring Solution Codechef in Python

``````for _ in range(int(input())):
x=input()
c=0
ans=0
l=len(x)
for i in range(0,l):
if (x[i] != x and x[i] != x[l-1]):
c=c+1
else:
c=0
ans=max(ans,c)
if ans==0:
print(-1)
else:
print(ans)``````

Program: Substring of a Substring Solution Codechef C++

``````#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
char first=s,last=s[s.size()-1];

int len=0,maxlen=-1;
for(int i=0;i<s.size();i++)
{
if(s[i]==first||s[i]==last)
{
if(len!=0)
{
maxlen=max(maxlen,len);
}
len=0;
}
else
{
len++;
}
}
cout<<maxlen<<endl;
}
return 0;
}``````

Program: Substring of a Substring Solution Codechef in Java

``````import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
String str=sc.next();
int count=0;
int max=0;
char first=str.charAt(0);
char last=str.charAt(str.length()-1);
for(int i=1;i<=str.length()-1;i++){
char ch=str.charAt(i);
if(ch!=first && ch!=last){
count++;
}else{
if(max<count)
max=count;
count=0;
}

}if(max==0){
max=-1;
}
System.out.println(max);
}
}
}``````