Coding Interview: How would you maintain distinct palindromic substrings online with an eertree?

Problem and Context

Given a stream s[0..n), one character is appended at a time. After each append, maintain the number of distinct palindromic substrings, occurrence counts for each palindrome, and the longest palindromic suffix of the current prefix. The solution must be online rather than re-enumerating all substrings after every append.

An eertree (palindromic tree) stores one node per distinct palindrome. Edges add the same character to both ends, while a suffix link points to the longest proper palindromic suffix. A strong answer explains the two sentinel roots, how an extendable suffix is found, and why at most one node is created per position.

What the Interviewer Evaluates

Correctly distinguishing the length -1 and length 0 roots.
Understanding last, the longest palindromic suffix, and suffix links.
Finding an extendable node and creating a transition during append.
Knowing the O(n) node, time, and space bounds under the append model.
Handling repeated characters, the empty string, alphabet representation, and count propagation.
Extending the structure to palindrome partitioning or sliding-window variants.

Clarifications to Ask First

Is the input a one-shot string or a stream that only appends on the right? Must the left side be deleted?
Should occurrences be counted by ending position or as final total frequencies?
Is the alphabet lowercase, Unicode, or arbitrary integer tokens?
Should the output contain the palindrome text, a node id, or only length and counts?
Are online minimum cuts required, or is maintaining the distinct-palindrome set enough?

30-Second Answer Framework

I use two roots: length -1 and length 0. Each ordinary node stores its palindrome length, a suffix link to the longest proper palindromic suffix, and character transitions. last is the longest palindromic suffix of the current prefix. When character c arrives, I follow suffix links until both sides can be wrapped by c; I reuse an existing transition or create one, then compute the new node's suffix link from the link chain. At most one distinct node can be added per position, so construction is O(n), and propagating occurrence counts in reverse suffix-link order gives final frequencies.

Step-by-Step Deep Dive

1. Two Roots and Node Fields

The odd root has length -1, acting as a sentinel that can be extended by any character. The even root has length 0 and represents the empty palindrome. Ordinary nodes store len, link, next, occ, and optionally an ending position. last starts at the even root.

2. Find an Extendable Suffix

After appending c at position pos, start from last and test whether the character just before the node's palindrome equals c. If not, set v = link[v] and continue. The first match is the longest palindromic suffix that can be extended.

text

while s[pos - 1 - len[v]] != c:
    v = link[v]

Implementations commonly prepend a sentinel outside the alphabet so the odd-root check never reads a negative index.

3. Add a Transition and Node

If next[v][c] already exists, it becomes the new last and its occ increases. Otherwise create a node of length len[v] + 2 and assign the transition. A length-one node links directly to the even root. For longer nodes, follow link[v] until the corresponding transition on c is found.

4. Why Only One Node Is Added

Every palindrome newly created by one append must end at the new character. Only the longest such palindrome is new; its shorter palindromic suffixes are already on the suffix-link chain. Therefore each position creates at most one distinct node, keeping the total at most n + 2.

5. Propagate Occurrence Counts

During the online pass, increment occ for the longest palindromic suffix ending at each position. After input ends, process nodes from longer to shorter and add occ[v] into occ[link[v]]. This transfers every occurrence to all of its palindromic suffixes. For only the distinct count, return the number of ordinary nodes.

6. Extend to Palindrome Partitioning

For minimum palindrome cuts, enumerate palindromes ending at each position by walking the last suffix-link chain and update dp[pos] = min(dp[pos - len[v]] + 1). A naive chain walk can become O(n^2). Series links can group equal length-difference runs, but the optimization should be chosen only after confirming the constraints.

7. Boundaries, Alphabet, and Complexity

The empty input has only the two roots. Repeated characters reuse transitions and must not create duplicate nodes. A small alphabet can use fixed arrays with O(n * alphabet) transition storage; a large alphabet needs a hash map or ordered map, giving expected O(n) or O(n log σ) behavior. Under right-only appends, construction is O(n) with expected constant-time hash transitions, and space is O(n) plus transition storage.

High-Quality Model Answer

I would first confirm right-only appends, the alphabet, and what an occurrence count means. The structure has length -1 and 0 roots; ordinary nodes represent distinct palindromes, and last is the current prefix's longest palindromic suffix. For each appended c, I follow suffix links to the longest node that can wrap around c. If its transition is absent, I create a node of length len + 2; a length-one node links to the even root, while longer nodes find their link through the parent's suffix-link chain. At most one node is created per position, so construction is linear. Recording each last and propagating counts from longer nodes to their links yields total frequencies. Left deletion, arbitrary insertion, or a large alphabet requires revisiting the structure and complexity.

Common Mistakes

Using one empty root → odd and even boundaries become awkward → keep both -1 and 0 roots.
Restarting from a root for every append → loses the online linear property → follow suffix links from last.
Treating last as the longest palindrome anywhere → it is only the longest palindromic suffix.
Linking a new node to its parent → link must target the longest proper palindromic suffix.
Incrementing every palindrome on every append → double counts → record ending nodes and propagate in reverse link order.
Applying a tiny fixed array to arbitrary Unicode → collisions or overflow → define encoding and mapping explicitly.

Follow-ups and Responses

When would you choose Manacher instead?

Manacher is a good fit for a static string when the only need is the longest radius at each center. An eertree represents every distinct palindrome and naturally supports online appends, node-level counts, and suffix-link queries.

How do you return the current longest palindrome text?

Store an ending position on each node. The pair of that position and len identifies a slice in the retained input. A stream that discards input needs a ring buffer or external storage.

Why propagate counts in reverse order?

Every occurrence of a longer palindrome is also an occurrence of each palindromic suffix on its link path. Processing longer nodes first ensures each child contribution is complete before it is added to its parent.

Can the structure delete from the left?

The ordinary eertree supports right appends only. A sliding window needs a double-ended variant or rebuilding/blocking; the choice depends on window size and deletion rate.

What changes with hash-map transitions?

Hash maps give expected O(1) transition lookup and expected O(n) construction. Worst-case behavior depends on the hash implementation. Ordered maps provide deterministic bounds with an O(log σ) factor.