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 $\operatorname{dp}[a][b]=0$. Choosing a later occurrence instead of $c$ only removes positions that could be used later, so considering the earliest such $c$ 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 $a$ 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