# CRZYSUBSTR Editorial

Setter: Bruce Wayne
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

2126

# PREREQUISITES:

Dynamic Programming, Strings

# PROBLEM:

Gotham City is the home of Batman, and Batman likes to keep his people together.

There are N houses in the city. The resident of the i^{th} house is of type A_i. It is known that people of the same type are friends and people of different types are not friends.

To maintain peace, Batman can do the following type of operation:

• Choose indices i and j (1\leq i \le j \le N) and reverse the substring A[i,j].

Determine the length of the longest range of friends after applying at most k operations on the string for all 0 \le k \le N.

# EXPLANATION:

First let’s see how we can increase the length of substrings having same character by the reversal operation as given in the question.
For a string say, s and for character say, x, we first take the longest and 2nd longest substrings having all characters as x. We are taking the longest and 2nd longest since we want to maximize the length of the substring formed in the given operation. Say they are at position i_1 and i_2 with length l_1 and l_2. Assuming i_1 is less than i_2, we can just reverse the substring s[i_1....i_2 - 1] to get substring of length (l_1+l_2) having all x. We can keep repeating this operation till we get the longest substring that contains all the x that are present in string s. Also we would observe that the number of operations required to get the above longest substring would be the number of substrings of x in the original string which would be always less than n, i.e the length of the string s.

Now coming back to this question, what we can do is repeat the operations as defined in the above paragraph for each character from a to z and for each operation take the length of the maximum possible substring that can be formed among a to z as our answer for that operation.

# TIME COMPLEXITY:

O(NlogN), for each test case.

# SOLUTION:

1 Like

Can someone please tell me why this solution is giving TLE.

void solve(int test_case){
ll n ; cin >> n ;
string s; cin >> s;

vector<pair<char,ll>> compress; compress.pb({s[0], 1});

for(ll i = 1 ; i < n ; i++){
if((*(--compress.end())).first == s[i]){
(*--compress.end()).second++;
}else{
compress.pb({s[i], 1});
}
}

map<char, vector<ll>> m;

map<char, ll> lele;

for(auto x : compress){
m[x.f].pb(x.s);
lele[x.f]++;
}

for(auto &x: m){
sort(rev(x.s));
for(ll i = 1 ; i < lele[x.f]; i++) x.s[i] += x.s[i-1];
}

ll ans = 0;
for(ll i = 0 ; i <= n ; i++){
for(auto x: m){
if(i < lele[x.f]){
ans = max(ans, x.s[i]);
}
}
cout << ans << " ";
}

cout << endl;

}


Instead of using a map, try hashing by making an array of vectors. The time complexity of map operation is O(log n), and the array is O(1).

1 Like

1. Map would take log(n) time, which should pass in the given time limits
2. I also used unordered map along with normal hash as well as custom hash, which didn’t work either as it should take O(1) per operation

In an ideal case, an unordered map takes O(1), that’s correct. But it’s not always the case. Please refer to Blowing up unordered_map, and how to stop getting hacked on it - Codeforces

According to my experience, I have seen multiple cases when my map (ordered/unordered) implementation gave TLE but vector implementation gave AC.
I would suggest that whenever you know what keys the map is going to have and its contiguous => use a vector, as it ensures O(1)

1 Like

Yeah, I agree but some solutions I saw, implemented exactly the same thing even using priority queue and maps

and also in this submission : link , I have used unordered_map along with the custom hash from the blog you mentioned, still giving TLE.

It would be great if I can get the test-case for which it is failing.

Here is the test case 12: JustPaste.it - Share Text & Images the Easy Way

1 Like

The page is no longer available…

What is wrong with my approach/code? Test cases 1,2,17,19 are giving WA.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int cases;
cin>>cases;
while(cases-- > 0){
int n;
cin>>n;
string s;
cin>>s;
if(n==1){
cout<<"1 11\n";
continue;
}
int ans=1,len=1,maxx[26]={0};
for(int x=0;x<n-1;x++){
maxx[s[x]-'a']++;
if(s[x]==s[x+1]) len++;
else len=1;
ans=max(ans,len);
}
len=1;
maxx[s[n-1]-'a']++;
int m=0,c=0;
for(int i=0;i<26;i++){
if(maxx[i]>m){
m=maxx[i];
c=i;
}
}
vector<int> v;
for(int i=0;i<n-1;i++){
if(s[i]==(char)(97+c)){
if(s[i]==s[i+1]) len++;
else{
v.push_back(len);
len=1;
}
}
}
if(len>1 || s[n-1]==(char)(97+c)) v.push_back(len);
sort(v.begin(),v.end());
int temp=0,i;
for(i=v.size()-1;i>=0 && v.size()-1-i<=n;i--){
temp+=v[i];
if(temp>ans) cout<<temp<<" ";
else cout<<ans<<" ";
}
for(;v.size()-1-i<=n;i--) cout<<temp<<" ";
cout<<"\n";
}
return 0;
}