PROBLEM LINK:
Practice
Author: Sidhant Bansal
Tester: tncks0121
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Strings, Hashing.
PROBLEM:
Consider an initially empty binary string. There are n queries. In each query, you are asked to either add a character 0/1 or remove the last character. After each query, find the largest palindromic substring of the string.
EXPLANATION:
Consider a base B and a prime mod. Precompute all powers upto n of B modulo mod. Also compute the powers of inverse of B upto n.
Let the current string be s_{0}s_{1} \ldots s_{L-1}. Let p_i be the largest palindromic substring of the prefix of length i. Maintain prefix hash of the string, H_i = \displaystyle \sum_{j=0}^{i} (s_j + 1) B^{i - j} .
Also maintain another set of prefix hashes found using modular inverse of B as the base. That is, also maintain G_i = \displaystyle \sum_{j=0}^{i} (s_j + 1) B^{j - i} .
Now, the hash of a substring s_l...s_ r is H_r - H_{l-1} B^{r - l + 1}, and the hash of the reverse of this substring, s_r \ldots s_{l} is \displaystyle B^{r - l} (G_r - G_{l-1} B^{l - r - 1}).
Using precomputed powers, both the hashes and reverse hashes can be found in O(1). Also, the arrays H and G can be maintained in O(1) per query, using H_i = H_{i - 1} B + s_i + 1 and G_i = G_{i-1} B^{-1} + s_i + 1.
Now, say the current largest palindromic substring is t. On appending a new character, the new longest palindromic substring has to have length \leq t + 2, as otherwise removing the first and last characters from this substring would give a palindromic substring of length > t in the original string, which is a contradiction.
So, on every append query, we only have to test whether the suffixes of length t + 1 and t + 2 are palindromes, which can be done in O(1). So, overall we can update p, H, G in O(1).
On each delete query, we just have to remove the last element from each of the arrays p, H, G.
The overall complexity would be O(n).
AUTHOR’S and TESTER’s SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here