思路：动态规划

定义$dp[i]$为前i个字符的完美字符串的数量

定义前缀数组$pre[idx]$为以字符idx为结尾的最多完美字符串的数量。

从第2个字符开始，遍历字符串s。对于每个字符s[i]，我们有两种情况需要考虑：

• 第一种情况，如果s[i]等于s[1]，那么dp[i]就等于1，因为我们可以将s[1..i]作为一个完美字符串。
• 第二种情况，如果s[i]不等于s[1]，那么dp[i]就等于pre[s[i]] + 1，因为我们可以将s[1..pre[s[i]]]作为一个完美字符串，然后将s[pre[s[i]]+1..i]作为另一个完美字符串。

更新前缀数组：对于每个字符s[i]，我们都需要更新pre[s[i]]，使其等于max(pre[s[i]], dp[i-1])。

输出结果：最后，我们输出dp[n]，即字符串s的最多完美字符串的数量

时间复杂度

$O(n)$

c++代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int n = s.size();
    vector<int> dp(n + 1, -1);

    vector<int> pre(26, -1);
    for (int i = 2; i <= n; ++i) {

        // 第一种情况，s[i] = s[1]
        if (s[i - 1] == s[0]) {
            dp[i] = 1;
        }

        int idx = s[i - 1] - 'a';
        // 第二种情况，dp[i] = pre[s[i]] + 1
        if (pre[idx] > 0) {
            dp[i] = pre[idx] + 1;
        }

        // 更新 pre[idx]
        if (dp[i - 1] > 0) {
            pre[idx] = max(pre[idx], dp[i - 1]);
        }
    }

    printf("%d\n", dp[n]);

    return 0;
}

python代码

s = input()
n = len(s)
dp = [-1] * (n + 1)
dp[0] = 0
MAX = {chr(i + ord("a")): (-1, -1) for i in range(26)}

for i in range(1, n + 1):
    MAXX, index = MAX[s[i - 1]]
    if MAXX != -1:
        dp[i] = dp[index] + 1
    # Always Keep Max
    if MAXX < dp[i - 1]:
        MAX[s[i - 1]] = (dp[i - 1], i - 1)
print(dp[-1])

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();

        int n = s.length();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);

        int[] pre = new int[26];
        Arrays.fill(pre, -1);

        for (int i = 2; i <= n; i++) {
            // 第一种情况，s[i] = s[1]
            if (s.charAt(i - 1) == s.charAt(0)) {
                dp[i] = 1;
            }

            int idx = s.charAt(i - 1) - 'a';
            // 第二种情况，dp[i] = pre[s[i]] + 1
            if (pre[idx] > 0) {
                dp[i] = pre[idx] + 1;
            }

            // 更新 pre[idx]
            if (dp[i - 1] > 0) {
                pre[idx] = Math.max(pre[idx], dp[i - 1]);
            }
        }

        System.out.println(dp[n]);
    }
}

题目内容

小红拿到了一个字符串，他希望通过切割操作将该字符串分割为完美字符串。完美字符串定义为长度大于等于2且首尾字符相同的串。

现在，小红想知道，在进行切割操作后，他所能得到的最多完美字符串的数量是多少？

输入描述

一个仅包含小写字母的字符串，长度不超过$200000$。

输出描述

如果无法切割且字符串本身不是完美字符串，请输出$-1$。

否则输出最终的完美字符串数量。

样例

输入输出示例仅供调试，后台数据一般不包含示例

输入

arcaea

输出

1

说明

本身即是完美字符串，且无法进行任何切制。

样例2

输入输出示例仅供调试，后台数据一般不包含示例

输入

abcb

输出

-1

说明

没有一种合法的切割方案。

https://www.bilibili.com/video/BV1N14y1R7R6