ADVITIYA4 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: ladchat
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

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)