Overlapping Intervals

Use $0$-based indices in this explanation.

Suppose the left endpoints of two consecutive currently open intervals are $a<b$. We first have to close the interval that starts at $a$, and then choose the left endpoint of the next interval.

Let $\operatorname{dp}[a][b]$ be the maximum number of intervals obtainable from a chain whose first two left endpoints are $a$ and $b$. Its value is $0$ if such a chain cannot be completed.

Let $c$ be the first position after $b$ such that $S_c=S_a$. If no such position exists, then . Choosing a later occurrence instead of only removes positions that could be used later, so considering the earliest such is sufficient.

The chain can end with exactly two intervals if there is an occurrence of $S_b$ after $c$. Otherwise, to create at least three intervals, choose a new left endpoint $d>c$. The remaining problem is exactly the state $(b,d)$, so

$$\operatorname{dp}[a][b]=\max\left(2,\ 1+\max_{d>c}\operatorname{dp}[b][d]\right).$$

The first term is available only when an occurrence of $S_b$ exists after $c$, and the second term is available only when a positive state exists in the range.

Maintain

$$\operatorname{suf}[b][x]=\max_{d\ge x}\operatorname{dp}[b][d].$$

Then every transition takes $O(1)$ time. Since $\operatorname{dp}[a][b]$ only refers to states $\operatorname{dp}[b][d]$ with $a<b<d$, process in decreasing order.

Take the maximum over all states. Separately handle the answer $1$ by checking whether any character occurs at least twice. The total time complexity is $O(N^2)$ and the memory complexity is $O(N^2)$.

Solution written by GPT5.6