思路: 动态规划

$dp[i]$ 表示前 i 个字符，使得串成为好串的最小删除数

对于第 $i$ 个字符，可以选择删除或者不删除。

如果删除第 $i$ 个字符：$dp[i]=dp[i-1]+1$
如果不删除第 $i$ 个字符，需要有第 $j$ 个字符满足 $s[j]=s[i], j<i$ 且 $j$ 尽可能大 ，即 $dp[i]=dp[j-1]+i-j-1$

两者取最小值即可。

时间复杂度：$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.length();

    vector<int> dp(n + 1, 0x3f3f3f3f);
    vector<int> last_pos(26, -1);

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int idx = s[i - 1] - 'a';

        dp[i] = dp[i - 1] + 1;

        if (last_pos[idx] != -1) {
            dp[i] = min(dp[i], dp[last_pos[idx] - 1] + i - last_pos[idx] - 1);
        }

        last_pos[idx] = i;
    }

    cout << dp[n] << "\n";

    return 0;
}

Python

s = input()
n = len(s)

# dp[i] 表示前 i 个字符，使得串成为好串的最小删除数
dp = [0x3f3f3f3f] * (n + 1)
last_pos = [-1] * 26

dp[0] = 0
for i in range(1, n + 1):
    # 拿到第 i 个字符的值
    idx = ord(s[i - 1]) - ord('a')

    # 删除第 i 个字符
    dp[i] = dp[i - 1] + 1

    # 当前面可以匹配时，尝试匹配
    if last_pos[idx] != -1:
        dp[i] = min(dp[i], dp[last_pos[idx] - 1] + i - last_pos[idx] - 1)

    last_pos[idx] = i

print(dp[n])

Java

import java.util.Arrays;
import java.util.Scanner;

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, 0x3f3f3f3f);
        int[] lastPos = new int[26];
        Arrays.fill(lastPos, -1);

        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int idx = s.charAt(i - 1) - 'a';

            dp[i] = dp[i - 1] + 1;

            if (lastPos[idx] != -1) {
                dp[i] = Math.min(dp[i], dp[lastPos[idx] - 1] + i - lastPos[idx] - 1);
            }

            lastPos[idx] = i;
        }

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

题目内容

小红有一个字符串，现在他想问你，最少需要删掉多少个字符，才可以使字符串变成一个好串。

对于小红来说，一个好串的长度必须是偶数，且满足当串的下标从 $0$ 开始，那么当 $i$ 是偶数，都有 $s_i=s_{i+1}$。

输入描述

一行，一个字符串，字符串长度不超过 $10^5$。

字符串只包含小写字母。

输出描述

一个数，表示最少需要删除的字符数量，才能使得字符串变为一个好串。

样例

输入

abbcdd

输出

2

说明

删除 a 和 c 后，字符串变为了 bbdd ，是一个好串。