PROBLEM LINK:
Setter: Erfan Alimohammadi, Rami
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Observation, RMQ or Segment Tree.
PROBLEM:
Given a string S of length N, you have to answer Q queries of the following form.
For each query, given two integers l and r, determine whether there exists any substring of String S_l, S_{l+1}, \ldots S_r, which is dominated by any character c. A string is dominated by a character c if c occur strictly more than half the length of string.
EXPLANATION
This editorial would be mostly observation, with little to code.
First of all, letās assume S[l, r] denote substring S_l, S_{l+1}, \ldots S_r.
Letās assume substring T with length x is dominated by some character c. WLOG assume x is even, this can be extended to odd x too. Letās split this substring into two equal parts of length x/2 each, letās call them left and right part.
Assume both left and right part are not dominated. Then, the maximum number of times c can occur in both strings is at most x/4 each, hence, we can have at most x/4+x/4 = x/2 occurrences of c at most, which implies that string T is not dominated by any character.
But this contradicts our assumption that T is dominated by character c.
This leads us to the conclusion that if a substring S is dominated, either left or the right half of the string is also dominated.
Hence, if we consider all substrings of S[l, r] with length >= 6, we can always have a string, it just suffices to check whether left or right half of string is dominated or not.
For strings of length 4 and 5, we can check whether they contain any substring of length 3 which is dominated or not as there cannot exist any substring of length 4 or 5 which is dominated, but no substring of such string of length 3 is dominated. (Similar proof as above). This cases arose because problem imposes the restriction on the minimum length of the dominated string.
Hence, to conclude from above, if a dominated substring T of length x> 3 exists, there also exists a substring with length 3 as a substring of T which is dominated.
So, all we need to do is consider each start point p and check whether substring S[p, p+2] is dominated or not. Letās precompute this.
Letās answer queries now. For each query, we are concerned for substring S[l, r]. If the length of this substring is less than 3, the answer is NO directly. Otherwise, we can consider all start points in the range [l, r-2] and if any string is dominated, substring S contains a dominated string, otherwise, no dominated string exists in this substring.
Noticing carefully, we need a range data structure, which can determine the range OR of range [l, r]. Any RMQ data structure such as sparse Table and Segment Tree would work.
Bonus What if there are updates, each update changing a single character at a specified position to c.
TIME COMPLEXITY
Time complexity is O((N+Q)*log(N)) per test case.
SOLUTIONS:
Setter 1 Solution
#include <bits/stdc++.h>
using namespace std;
const int max_n = 100100;
int ans[max_n];
int ln[max_n];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
int cnt = 0;
while(cnt < t)
{
int n,q;
cin >> n >> q;
string s;
cin >> s;
ans[s.length()-1] = s.length();
for(int i=s.length()-2;i>=0;i--)
{
if(s[i] == s[i+1])
ans[i] = i , ln[i] = 1;
else if(i != s.length() - 2 && s[i] == s[i+2])
ans[i] = i , ln[i] = 2;
else ans[i] = ans[i+1] , ln[i] = ln[i+1];
}
for(int i=0;i<q;i++)
{
int l , r;
cin >> l >> r;
l-- , r--;
if(r - l + 1 >= 3 && ans[l] + ln[l] <= r)
cout <<"YES" << "\n";
else
cout <<"NO" << "\n";
}
cnt++;
}
return 0;
}
Setter 2 Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;
char s[1001000];
int ok1[1001000];
int ok2[1001000];
int main() {
int t;
cin>>t;
int n,q;
while(t--){
scanf("%d%d",&n,&q);
scanf("%s",s+1);
for(int i=0 ;i <=n+2; i++)ok1[i] = ok2[i] = 0;
for(int i=1 ;i <=n ;i ++){
ok1[i] = ok1[i-1];
if(i+1 <= n && s[i] == s[i+1])ok1[i]++;
}
for(int i=1 ;i <=n ;i ++){
ok2[i] = ok2[i-1];
if(i+2 <= n && s[i] == s[i+2])ok2[i]++;
}
int l,r;
while(q--){
scanf("%d%d",&l,&r);
if(r-l+1 < 3){
printf("NO\n");
continue;
}
if(ok1[r-1]-ok1[l-1] > 0)printf("YES\n");
else if(ok2[r-2]-ok2[l-1] > 0)printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define endl '\n'
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int good[123456];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,q;
cin>>n>>q;
int i;
string s;
cin>>s;
rep(i,n+10){
good[i]=0;
}
rep(i,n-1){
if(s[i]==s[i+1])
good[i+1]=1;
}
rep(i,n-2){
if(s[i]==s[i+2])
good[i+1]=1;
}
f(i,1,n+1){
good[i]+=good[i-1];
}
int l,r;
rep(i,q){
cin>>l>>r;
if(l+1>=r){
cout<<"NO"<<endl;
continue;
}
if(s[r-1]==s[r-2]){
cout<<"YES"<<endl;
continue;
}
if(good[r-2]>good[l-1]){
cout<<"YES"<<endl;
continue;
}
cout<<"NO"<<endl;
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class RICHSTR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), q = ni();
String s = n();
int m = 1;
while(m<=n)m<<=1;
boolean[] b = new boolean[m<<1];
for(int i = 0; i< n-2; i++)
if(s.charAt(i) == s.charAt(i+1) || s.charAt(i+1) == s.charAt(i+2) || s.charAt(i) == s.charAt(i+2))b[i+m] = true;
for(int i = m-1; i> 0; i--)b[i] = b[i<<1]|b[i<<1|1];
while(q-->0){
int l = ni()-1, r = ni()-3;
pn(query(b, l, r, 0, m-1, 1)?"YES":"NO");
}
}
//Returns OR of all booleans in range[l, r]
boolean query(boolean[] b, int l, int r, int ll, int rr, int i){
if(l > r)return false;
if(l == ll && r == rr)return b[i];
int mid = (ll+rr)/2;
if(r <= mid)return query(b, l, r, ll, mid, i<<1);
else if(l > mid)return query(b, l, r, mid+1, rr, i<<1|1);
else return query(b, l, mid, ll, mid, i<<1) || query(b, mid+1, r, mid+1, rr, i<<1|1);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
static double eps = 1e-8;
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 RICHSTR().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, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 
