PROBLEM LINK:
Setter: Shahjalal Shohag
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Simple
PREREQUISITES:
Greedy and Ad-hoc
PROBLEM:
You are given a string S of length N. You have to determine if it is possible to divide the string into two non-empty parts A and B such that :
- A + B = S
- B is a substring of A
EXPLANATION:
If you observe carefully, you will notice that string A is a prefix and string B is a suffix of S.
Now suppose for a suffix of length L the conditions are satisfied then you can see that the conditions are also satisfied for suffix of length L-1. This observation gives us a hint to greedily select the smallest possible suffix and that is a single character which is the last character of the string S.
So string A is the whole string S except the last character and string B is the last character of S. Now you can simply check if it satisfies the conditions, by checking whether the last character is present in string A, and if it is present then the answer is “YES” else the answer is “NO”.
You can do the above process by counting the frequency of the last character in string S and if it’s FREQ_{last char} \geq 2, then the answer is “YES” else the answer is “NO”.
TIME COMPLEXITY:
- Time complexity per test case is O(N).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
assert(1 <= t && t <= 10000);
int sum = 0;
while (t--) {
int n; cin >> n;
assert(2 <= n && n <= 100000);
sum += n;
string s; cin >> s;
assert(s.size() == n);
vector<int> cnt(26, 0);
for (auto c: s) {
assert(c >= 'a' && c <= 'z');
cnt[c - 'a']++;
}
if (cnt[s.back() - 'a'] > 1) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
assert(1 <= sum && sum <= 1000000);
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
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;
}
assert(l<=x && x<=r);
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,' ');
}
int sum_n=0;
void solve() {
int n=readIntLn(1,100000);
sum_n+=n;
assert(sum_n<=1000000);
string s=readStringLn(n,n);
for(int i=0; i+1<sz(s); i++)
if(s[i]==s.back()) {
cout<<"YES"<<endl;
return;
}
cout<<"NO"<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
int t=1;
// cin>>t;
t=readIntLn(1,10000);
fr(i,1,t) {
solve();
}
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
void Solve() {
int n;
string s;
cin >> n >> s;
char last_char = s[n-1];
int count = 0;
for(int i = 0; i < n; i ++) {
if(s[i] == last_char) count ++;
}
if(count >= 2) cout << "YES\n";
else cout << "NO\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int test_case = 1;
cin >> test_case;
for(int i = 1; i <= test_case; i ++) {
Solve();
}
return 0;
}
VIDEO EDITORIAL (Hindi):
VIDEO EDITORIAL (English):
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 
