SPLITIT - Editorial

PROBLEM LINK:

Practice
Contest

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. :smile:

4 Likes

If any one wants this

Instead of traversing the array again, we can use an array to count the occurrence of all the character in the array and subtract 1 from the index “x” equivalent to the last character of the string and check whether ar[x]>0 if it is print yes else no

Here is a link to my solution

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

just check if last character is present in the substring that starts form index 0 and has a length n-1

1 Like

how do you guys know that we just have to traverse the char array with last character,i have tried it for 1.30 hours and i give up :upside_down_face: :no_mouth:

2 Likes

Forget char array , since we know that B is a suffix than obviously atleast last character of it must be present in the entire string , eg for abcdefghijkla since last char ‘a’ is also present in the string if traverse it from 0 to n-2 , you can easily write that as abcdefghijkl + a = abcdefghijkla , hence you just had to check the presence of last char in the string .

1 Like

thank you bro now i get it :blush:

i am not understanding why my code was giving tle
here is my code
https://www.codechef.com/viewsolution/39037296

Your code runs in O(n^2) complexity. The line " if(b in a)" works in linear time O(n), and also you’re iterating over the original string, which is also O(n). Since the if condition is nested, the overall runtime becomes O(n^2), and you’re getting a TLE.

thus according to you then following code must also O(n^2)
but it got accepted why???
the code is here
https://www.codechef.com/viewsolution/39038712

You are doing
if b in a
which is O(n), so overall complexity is O(n^2).
Whereas, the code you gave here just checks if s[i]==character, so overall its complexity is O(n)

Now I get it

Here is the editorial for python3:
https://cpblogs-witharyan.blogspot.com/2020/10/split-str-ing-codechef-editorial-and.html
I am new to blogging so please encourage me with your comments

1 Like

#include

using namespace std;

int main() {
// your code goes here
int t,k;
int flag =0;
string str;

cin>>t;


while(t--)
{
    cin>>k;
    cin>>str;
    
    for(int i =0;i<k-1;i++)
    {
        if(str[k-1] == str[i])
        {
            flag = 1;
            break;
        }
        
    }
    
    if(flag == 1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
        
    flag = 0;
}

return 0;

}

please tell me…where is the problem