PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: inov_360
Testers: IceKnight1093, tabr
Editorialist: IceKnight1093
DIFFICULTY:
1566
PREREQUISITES:
None
PROBLEM:
A string is called boring if all its characters are the same.
Given a string S, find the longest boring substring of S that appears more than once.
EXPLANATION:
First, note that boring substrings corresponding to different characters are independent.
So, let’s fix a character, say c, and compute the longest boring substring consisting of c that appears more than once. We can then repeat this for every letter and take the maximum across all answers.
Solving this problem hinges on a single major observation:
Suppose S has a boring substring of length k. S then contains two boring substrings of length k-1: the first k-1 and the last k-1 characters of the substring.
So, let’s fix a character c and compute the longest boring substring of S consisting of c.
This is fairly easy to do in \mathcal{O}(N) by just iterating across the string and maintaining the current length of the boring substring: increase it by 1 when you encounter a c and reset it to zero otherwise.
Let this length we compute be k. Then,
- If there are two separate boring substrings of length k, the answer for c is k
- Otherwise, the answer for c is k-1.
All that remains is to check the first condition. This is fairly easy to do: for example, when computing k, keep a second variable that counts the number of occurrences of k and update it each time you update k.
The above approach is \mathcal{O}(26N), but it’s not hard (though also unnecessary) to optimize it to \mathcal{O}(N) by solving for all characters simultaneously.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Setter's code (C++)
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define db double
#define el "\n"
#define ld long double
#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++)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef vector< long long > vi;
typedef pair<long long, long long> ii;
typedef priority_queue <ll> pq;
#define o_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1000000007;
const ll INF = (ll)1e18;
const ll MAXN = 1000006;
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;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
cin >> T;
while(T--){
int n;
cin>>n;
string s;
cin>>s;
assert(s.length()==n);
for(auto h:s){
assert(h>='a' && h<='z');
}
vector<int>len(26, 0);
vector<int>cnt(26, 0);
int curr = 1;
rep_a(i,1,n+1){
if(s[i]!=s[i-1] || i==n+1){
int id = (int)(s[i-1]-'a');
if(curr>len[id]){
len[id]=curr;
cnt[id]=1;
}
else if(curr==len[id]){
cnt[id]++;
}
curr=1;
}
else curr++;
}
int mx = 0, id, ans;
rep(i,26){
if(len[i]>mx){
mx = len[i];
if(cnt[i]>1){
ans = len[i];
}
else{
ans = len[i]-1;
mx--;
}
}
}
cout<<ans<<el;
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
// cerr << res << endl;
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1000);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 2e5);
in.readEoln();
sn += n;
string s = in.readString(n, n, in.lower);
in.readEoln();
vector<vector<int>> c(26);
for (int i = 0, j = 0; i < n; i = j) {
while (j < n && s[i] == s[j]) {
j++;
}
c[s[i] - 'a'].emplace_back(j - i);
}
int ans = 0;
for (int i = 0; i < 26; i++) {
sort(c[i].rbegin(), c[i].rend());
if (c[i].size() >= 1) {
ans = max(ans, c[i][0] - 1);
}
if (c[i].size() >= 2) {
ans = max(ans, c[i][1]);
}
}
cout << ans << '\n';
}
assert(sn <= 5e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
mx = [[0, 0] for _ in range(26)]
curch, curlen = s[0], 0
for i in range(n):
if s[i] == curch: curlen += 1
if i == n-1 or s[i] != s[i+1]:
pos = ord(curch) - ord('a')
if curlen > mx[pos][0]:
mx[pos] = [curlen, 0]
if curlen == mx[pos][0]: mx[pos][1] += 1
if i < n-1: curch, curlen = s[i+1], 0
ans = 0
for i in range(26):
if mx[i][1] > 1: ans = max(ans, mx[i][0])
else: ans = max(ans, mx[i][0] - 1)
print(ans)