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.