hackercupai/hackercup huggingface dataset:
As in Chapter 2, we'll think of \(G(S)\) as being made up of a sum of products based on relevant pairs of "X"s and "O"s (which necessitate hand switches in between typing them). Each such pair of letters at indices \(a\) and \(b\) in \(S\) (such that \(a \lt b\)) contributes an addition of \(a * (|S| - b + 1)\) to \(G(S)\). We'll refer to \(a\) as the pair's \(L\) value, and to \((|S| - b + 1)\) as its \(R\) value.

We'll need a representation of a string \(S\) which allows us to support both types of updates while maintaining the value of \(G(S)\), but without an \(O(|S|)\) representation of the exact full content of \(S\) (as it can grow far too large). Our representation \(Z(S)\) shall consist of the following values (all stored modulo \(1{,}000{,}000{,}007\)):
- \(|S|\)
- \(I_1(S)\) and \(V_1(S)\), the index and value of the first non-"F" letter in \(S\) (if any)
- \(I_2(S)\) and \(V_2(S)\), the index and value of the last non-"F" letter in \(S\) (if any)
- \(P(S)\), the number of relevant letter pairs
- \(L'(S)\), the sum of pairs' \(L\) values
- \(R'(S)\), the sum of pairs' \(R\) values
- \(G(S)\)

Given two strings \(S_1\) and \(S_2\) to concatenate into \(S_1 S_2\), we'll seek an algorithm to compute \(Z(S_1 S_2)\) given \(Z(S_1)\) and \(Z(S_2)\). This will be enough to support both types of updates: duplicating \(S\) is equivalent to concatenating \(S\) and \(S\), while appending a single letter \(c\) to \(S\) is equivalent to concatenating \(S\) and \(c\). Note that \(Z(\)""\()\) and \(Z(c)\) (for any letter \(c\)) are simple to compute.

We can observe that concatenating \(S_1\) and \(S_2\) yields a string with all of the relevant letter pair from each of \(S_1\) and \(S_2\), plus at most one additional pair spanning between the two strings. If we ignore the possibility of that additional pair for now, the values of \(Z(S_1 S_2)\) can otherwise be computed without much trouble:
- \(|S_1 S_2|\) and \(P(S_1 S_2)\) are simply added together from those of \(S_1\) and \(S_2\)
- \(I_1(S_1 S_2)\) and \(V_1(S_1 S_2)\) are inherited from those of either \(S_1\) or \(S_2\) (with \(|S_1|\) added to \(I_1\) in the latter case), with \(I_2\) and \(V_2\) handled similarly
- \(L'(S_1 S_2) = L'(S_1) + L'(S_2) + P(S_2)*|S_1|\), with \(R'\) handled similarly
- \(G(S_1 S_2) = G(S_1) + G(S_2) + L'(S_1)*|S_2| + R'(S_2)*|S_1|\)

If \(V_2(S_1)\) and \(V_1(S_2)\) both exist and differ from one another, then an additional pair between indices \(I_2(S_1)\) and \(|S_1| + I_1(S_2)\) should be accounted for. This involves fairly simply updates to \(P(S_1 S_2)\), \(L'(S_1 S_2)\), \(R'(S_1 S_2)\), and \(G(S_1 S_2)\).

We can follow this process to arrive at \(Z(S)\) for the final string \(S\) (including the value of \(G(S)\)) in \(O(N)\) time.

[See David Harmeyer's solution video here](https://youtu.be/O1giTvqaxzM).