Substring of a Substring Solution Codechef

by

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

Leave a Comment

eighteen + 14 =