Substring of a Substring Codechef Solution | MARCH LONG CHALLENGE

Codechef
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[0] && 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() {
	// your code goes here
	int T;
	cin >> T;
	while(T--) {
	    Ans();
	}
	return 0;
}

Java

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

class h {
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        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);
            }
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(
                    new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 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 {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Python

for _ in range(int(input())):
    s=input()
    f=s[0]
    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)

Substring of a Substring Codechef Solution Tutorial

Read More Post Here

Leave a Comment

Your email address will not be published. Required fields are marked *

x