# Substring of a Substring Codechef Solution | MARCH LONG CHALLENGE Share:

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++

``````#include <iostream>
using namespace std;

void Ans() {
string x;
cin >> x;
int l = x.size();
int c = 0;
int ans = 0;
for(int i=0; i<l; i++) {
if(x[i]!=x && x[i]!=x[l-1]){
c = c+1;
}else {
c=0;
}
ans =max(ans, c);

}
if(ans == 0) {
cout << -1 << endl;
}else {cout << ans << endl;}
}

int main() {
int T;
cin >> T;
while(T--) {
Ans();
}
return 0;
}
``````

#### Java

``````import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.*;

class h {
public static void main(String[] args) {
int tc = sc.nextInt();
while (tc-- > 0) {
String str = sc.next();
char p = str.charAt(0);
char s = str.charAt(str.length() - 1);
int count = 0;
int max = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) != p && str.charAt(i) != s) {
count++;
} else {
max = Math.max(count, max);
count = 0;
}
}
if (max != 0) {
System.out.println(max);
} else {
System.out.println(-1);
}
}
}

StringTokenizer st;

}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}``````

#### Python

``````for _ in range(int(input())):
s=input()
f=s
l=s[-1]
mx=0
count=0
for a in s:
if a==f or a==l:
if count>mx:
mx=count
count=0
else:
count+=1
print(-1) if mx==0 else print(mx)``````