Page Contents
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[0] 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[0],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); } } }
Codechef March Long Challenge 2022 Solutions
- Bath in Winters Solution Codechef
- Discus Throw Solution Codechef
- Count the Ones Solution Codechef
- MEX on Trees Solution Codechef
- Subarray XOR Solution Codechef
- Substring of a Substring Solution Codechef
- Exact Marks Solution Codechef
- Akash and Function Solution Codechef
- Akash and Missing Class Solution Codechef
- Wordle Solution Codechef