# BINPALIN - Editorial

**URL:** <https://discuss.codechef.com/t/binpalin-editorial/47263>\
**Category:** editorial\
**Tags:** icpc2019, medium-hard, string-hashing, gw19mos\
**Created:** [December 20, 2019, 5:25pm UTC](https://discuss.codechef.com/t/binpalin-editorial/47263 "2019-12-20T17:25:47Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![jtnydv25](https://discuss.codechef.com/user_avatar/discuss.codechef.com/jtnydv25/32/111254_2.png) [@jtnydv25](https://discuss.codechef.com/u/jtnydv25)\
**Post date:** [December 20, 2019, 5:25pm UTC](https://discuss.codechef.com/t/binpalin-editorial/47263/1 "2019-12-20T17:25:47Z")

</div>

**PROBLEM LINK:**  
[Practice](https://www.codechef.com/problems/BINPALIN)

**Author:** [Sidhant Bansal](https://www.codechef.com/users/sidhant007)  
**Tester:** [tncks0121](https://www.codechef.com/users/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](https://ideone.com/FbxVg2)  
Tester’s solution can be found [here](https://ideone.com/21XLLs)
