Tester: apoorv_me
Editorialist: iceknight1093

TBD

None

# PROBLEM:

A string is called beautiful if all its characters are the same.
You’re given a string S and Q updates to it, each one appending a character.
Before any updates, and after each update, find the longest beautiful substring of S.

# EXPLANATION:

Finding the longest beautiful substring of S in \mathcal{O}(N) time is relatively simple: break S into “blocks” of equal characters, and find the longest one among them.
For example, S = \texttt{aaaabbacccae} breaks into \texttt{aaaa}, \texttt{bb}, \texttt{a}, \texttt{ccc}, \texttt{a}, \texttt{e}.

This way, the answer for the initial string S can be computed.
Now, note that appending a character to the end really doesn’t change much about these blocks. In particular, suppose you append character ch to S. Then,

• If ch equals the existing last character of S, that last block increases in length by 1.
• Otherwise, it creates a new block of length 1 by itself.

So, maintain three quantities: the answer (\text{ans}), the last character of S (\text{lst}), and the final block length of S (\text{len}).
Then, when appending ch to S:

• If ch = \text{lst}, set \text{len} \to \text{len} + 1, since the block extends.
• Otherwise, set \text{len} = 1 and \text{lst} = ch.
• Then, set \text{ans} \to \max(\text{ans}, \text{len}) to account for this change of the last block.

This way, each update is processed in constant time.

# TIME COMPLEXITY:

\mathcal{O}(N + Q) per testcase.

# CODE:

Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll T;
cin >> T;
while (T--)
{
ll n, q;
cin >> n >> q;
string s;
cin >> s;
char prev = s[n - 1];
ll maxi = 1;
ll ct = 0;
char temp = s[0];
for (ll i = 0; i < n; i++)
{
if (s[i] == temp)
{
ct++;
maxi = max(maxi, ct);
}
else
{
ct = 1;
}
temp = s[i];
}
cout << maxi << " ";
while (q--)
{
char ch;
cin >> ch;
if (ch == prev)
{
ct++;
}
else
{
ct = 1;
}
prev = ch;
maxi = max(maxi, ct);
cout << maxi << " ";
}
cout << endl;
}
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n, q = map(int, input().split())
s = list(input())
ans, suf = 0, 0
for i in range(n):
if i == 0 or s[i] != s[i-1]: suf = 1
else: suf += 1
ans = max(ans, suf)
output = [ans]
for i in range(q):
c = input()
if c != s[-1]: suf = 1
else: suf += 1
ans = max(ans, suf)
s.append(c)
output.append(ans)
print(*output)