解题思路

令 $dp[i]$ 表示把前缀 $s[0..i-1]$（长度为 $i$）切成同端片段的最多段数；若无法切分则为 $-1$。空前缀 $dp[0]=0$。

对每个字符 $c$，记录一个二元组 $(\textit{MAX}[c], \textit{index}[c])$：在以往某个位置 $index$ 处，字符恰好为 $c$，且当时前缀 $s[0..index-1]$ 的最优段数为 $\textit{MAX}$。

从左到右扫描，处理第 $i$ 个字符 $s[i-1]$ 时：

• 若该字符曾经作为某段的起点被记录过（$\textit{MAX}\ne -1$），则可以把 $s[index..i-1]$ 作为新的一段同端片段（首尾都是这个字符，且长度至少为 2），于是 $dp[i]=dp[index]+1$。