SUBSTRING - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Practice

Setter: RIFAT
Testers: Tejas Pandey and Abhinav sharma
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Observation

PROBLEM

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.

QUICK EXPLANATION

  • Any substring will satisfy all conditions if it doesn’t contain any occurrence of the first or last character of the given string.
  • We can mark all occurrences of first or last characters as 0, rest as 1, so the problem becomes to find the largest substring with all 1.
  • If no 1 is present, it is impossible to choose any substring.

EXPLANATION

Understanding the conditions

Let’s call a string valid if it satisfies all three conditions, otherwise invalid.

Let’s consider a substring S_{l, r}, which only violates the 2nd condition. This means that S_{l, r} contains a substring, which is a prefix of S. The smallest prefix of S is single character S_{0,0} itself. Since substring S_{l, r} contains a prefix of S, it contains character S_{0, 0}.

Let’s try converse of this now. What happens if substring S_{l, r} does not contain the character at the first position of S. All prefixes of S include that character, but S_{l, r} does not. Hence, no prefix of S is present in S_{l, r}.

So we can see that the second condition boils down to checking whether the substring chosen should not contain the first character of S.

Applying the same reasoning on the 3rd condition, we can see that chosen substring should not contain the last character of S.

Hence, assuming first character c_f and last character c_l, we need to find length of largest substring of S not containing c_f and c_l.

Reduction to a simpler problem

Now, the actual character in the given string does not matter, the only thing that matters is whether they are the same as c_f or c_l matters. We can build a binary string T, where T_i = 0 denotes that we cannot include i-th character and T_i = 1 denotes that we can include i-th character in substring.

The final answer would be the length of the longest substring with all ones. This is a well-known simple problem. We can divide T into blocks of the same character and consider the largest block of 1.

One similar problem can be found here.

TIME COMPLEXITY

The time complexity is O(|S|) per test case.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

void solve() {
    string s; cin >> s;
    int n = s.size();

    set <char> st(s.begin(), s.end());
    if (st.size() == 1 or (st.size() == 2 and s[0] != s.back())) {
	    cout << "-1\n";
	    return;
    }

    string t, tt;
    int ans = 0;
    for (int i = 1; i < n; i++) {
	    if (s[i] == s[0] or s[i] == s.back()) {
		    if (tt.size() > t.size() or (tt.size() == t.size() and tt < t))
			    t = tt;
		    tt.clear();
	    }
	    else {
		    tt.push_back(s[i]);
	    }
    }

    cout << t.size() << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int ts;
    cin >> ts;
    while (ts--) {
	    solve();
    }

    return 0;
}
Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;


/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}


/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 10000;
const int MAX_N = 1000000;
const int MAX_SUM_N = 1000000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_len=0, max_len = 0;

void solve()
{
    string s = readStringLn(1, MAX_N);
    int n = s.size();
    sum_len += n;
    max_len = max(max_len, n);
    assert(sum_len <= MAX_SUM_N);
    int ans = -1;
    int l = 1,r = 1;
    if(n > 1 && (s[1] == s[0] || s[1] == s[n - 1])) l++;
    else if(n > 1) ans = 1;
    while(r < n - 1) {
        r++;
        while(l <= r && (s[r] == s[0] || s[r] == s[n - 1])) l++;
        if(l <= r)
            ans = max(ans, r - l + 1);
    }
    cout << ans << "\n";
}

signed main()
{
    //fast;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif


    int t = readIntLn(1, MAX_T);

    for(int i=1;i<=t;i++)
    {
        solve();
    }
    cerr << max_len << " " << sum_len << "\n";
    assert(getchar() == -1);
}
Tester's Solution 2
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
 
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 998244353;

ll po(ll x, ll n){ 
    ll ans=1;
    while(n>0){ if(n&1) ans=(ans*x)%mod; x=(x*x)%mod; n/=2;}
    return ans;
}



void solve()
{   
    
    string s = readStringLn(1, 1e6);

    for(auto h:s) assert(h>='a' && h<='z');

    int n = s.length();
    sum_n += n;
    max_n = max(max_n, n);

    int curr = 0 , ans = 0;
    rep_a(i,1,n-1){
        if(s[i]==s[0] || s[i]==s[n-1]) curr=0;
        else curr++;

        ans = max(ans, curr);
    }

    if(ans==0) ans=-1;

    cout<<ans<<'\n';
}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,10000);
    
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    //assert(getchar() == -1);
    assert(sum_n<=1e6);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_n <<'\n';
    cerr<<"Maximum length : " << max_n <<'\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class SUBSTRING{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        String S = n();
        if(S.length() <= 2){
            pn(-1);
            return;
        }
        int ans = 0;
        for(int i = 0, ii = 0; i< S.length(); i = ii){
            while(ii < S.length() && (S.charAt(ii) == S.charAt(0) || S.charAt(ii) == S.charAt(S.length()-1)))ii++;
            i = ii;
            while(ii < S.length() && !(S.charAt(ii) == S.charAt(0) || S.charAt(ii) == S.charAt(S.length()-1)))ii++;
            ans = Math.max(ans, ii-i);
        }
        if(ans == 0)pn(-1);
        else pn(ans);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new SUBSTRING().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

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

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

I also had the same thing in mind. But my solution could only pass test case 1 and 10.
Can someone correct me ?

#include <bits/stdc++.h>

#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sp ' '
#define nl '\n'
#define ll long long
#define ull unsigned long long
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define range(a , min , max) a >= min and a <= max

using namespace std;

void solve() {
	string s;
	cin >> s;
	
	int len = s.length();
	
	char start = s[0];
	char end = s[len - 1];
	
	int max_ = 0;
	int cnt = 0;
	
	for (int i = 1 ; i < len - 1 ; i ++) {
		if (s[i] != start and s[i] != end) {
			cnt ++;	
		}
		else {
			max_ = max(max_ , cnt);
			cnt = 0;
		}
	}
	
	if (max_)
		cout << max_ << nl;
	else
		cout << -1 << nl;
}

int main()
{
    int tc;
    cin >> tc;

    while(tc--) {
		solve();
	}

    return 0;
}

okay so on traversing from 0 to length - 1 on the string I passed all the test cases. But my initial solution of traversing on 1 to length - 2 on the string was failing.

Why’s that ?

/*

Name : Satyam Shukla

*/

/*

to get x/y as an integer do this --> (x+y-1)/y

*/

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000007

#define fasio                         \

    ios_base::sync_with_stdio(false); \

    cin.tie(NULL);

#define fori(i, a, b) for (int i = a; i < b; i++)

#define endl "\n"

#define elif else if

const ll INF = 1e17;

const ll NINF = (-1) * INF;

typedef pair<ll,pair<ll,ll>> ppi;

#define LIMIT 1000000

long long i, j;

long long prime_flag[LIMIT];

void calculate_prime_flag()

{

    prime_flag[0] = prime_flag[1] = 1;

    for (i = 2; i < LIMIT; i++)

    {

        // to avoid overflow u can also set i*i<LIMIT

        if (prime_flag[i] == 0)

        {

            for (j = i * i; j < LIMIT; j += i)

            {

                prime_flag[j] = 1;

            }

        }

    }

    //0 -> prime

    //1 -> not prime

}

long long unsigned int power(long long unsigned int x, long long unsigned int y, long long unsigned int p)

{

    int res = 1; // Initialize result

    x = x % p; // Update x if it is more than or

               // equal to p

    if (x == 0)

        return 0; // In case x is divisible by p;

    while (y > 0)

    {

        // If y is odd, multiply x with result

        if (y & 1)

            res = (res * x) % p;

        // y must be even now

        y = y >> 1; // y = y/2

        x = (x * x) % p;

    }

    return res;

}

//For Codeforces A problme -- > if you figured out what to do then its good but if u are not able to figure it out then try to

//observe the pattern in the test cases

//So first task after reading question is if it is an algorithmic style then do code but if not then try to observe from test cases

void solve()

{

    string str;

    cin>>str;

    ll N = str.length();

    if(N==1||N==2)

    {

        cout<<-1<<endl;

    }

    else

    {

        vector<string> vp;

        char a = str[0];

        char b = str[N-1];

        string temp = "";

        for(auto &value:str)

        {

            if(value==a||value==b)

            {

                if(temp!="")

                {

                    vp.push_back(temp);

                }

                temp="";

            }

            else

            {

                temp+=value;

            }

        }

        if(temp!="")

        {

            vp.push_back(temp);

        }

        if(vp.size()==0)

        {

            cout<<-1<<endl;

        }

        else

        {

            ll ans = INT_MIN;

            for(auto &value:vp)

            {

                if(value.length()>ans)

                    ans = value.length();

            }

            if(ans<=0)

                cout<<-1<<endl;

            else

                cout<<ans<<endl;

        }

    }

}

int main()

{

    ll T;

    cin >> T;

    while (T-- > 0)

    {

        solve();

    }

    // your code goes here

    return 0;

}

Anyone Please do tell me where my code is going wromng

Hey, since you are iterating only till len-2, there can be a case where cnt is greater than max\_ at i==(len-2) but the loop breaks and cnt does not gets updated.

Simply iterating till len-1 or putting

max\_ = max(max_ , cnt)

will solve the problem.

It is because there can be a case where cnt is greater than max_ when i is equal to (len-2) but the loop breaks and cnt does not gets compared and updated to the new value since the else condition in never executed after that.

But if you traverse till length -1, the else condition is executed and the cnt variable gets updated before printing.

Initializing ll ans with INT_MIN causes ambiguity whenever you check it with value.length() as they both are different datatypes and to and INT_MIN gets type-casted to unsigned int.

Now since INT_MIN is much less than 0, the typecasting makes its value ambiguous while comparing and the comparison always returns FALSE.
So please initialize the value of ans as 0.

https://www.codechef.com/viewsolution/67038905

I tried something