我们先来思考一件事，如果我们遍历到一个下标$p$，$p$之前的部分已经按最优情况删过字符，那么接下来我们还需不需要去动前面的字符.............................不需要对吧，我们只需要去考虑如何删后面的字符来保证最优解

接下来看一个例子 “abcbdacabdba” 应该如何删字符...................首先第三个字符$c$肯定是要删掉的对吧，后面的部分才是重点 如果我们什么都不管一定要留$d$需要删去中间的4个字符加上后面的$ba$两个，这部分共需要删掉6个字符 但是如果我们干脆不要$d$呢，当你删掉$d.c..d.a$时这部分只需要删4个

那么删字符的思路是什么呢？ 当我们遍历到一个偶数位字符与下一个字符不一样的时候，向后遍历找到第一对一样的字符，因为你删字符影响的范围最小，所以对后面的影响就最小，这样可以保证后面删的也尽可能少。 什么意思，比如上面的例子： 遍历到$da$开始找发现第一对字符是$.a.a$，那如果把中间的$d.b.$删掉，对后面字符串的影响是不是最小的

根据以上思路我们可以先对字符串进行一个预处理，先计算好每个字符之前最后一个一样的字符在哪，之后找的时候直接用就好了，这样可以省去大部分时间

下面是代码

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

string s;
int cnt;
int c[100],last[1000001];

signed main(){
	cin>>s;
	for(int i=0;i<s.size();i++){
		last[i]=c[s[i]-'a'];
		c[s[i]-'a']=i;  //更新每个字符最后出现的位置
	}
	last[s.size()]=s.size()-1;
  /*对于最后遍历到尾也没有一对字符的时候应该把这一串都删掉
  为了偷懒，直接加一个空字符让它指向字符串尾，遍历到它时后面的判断一定成立*/
	for(int i=1;i<s.size();i+=2){
		if(s[i]!=s[i+1]){
			for(int j=i+2;j<=s.size();j++){
				if(last[j]>=i){//只有last[j]>=i的时候，保证不会去动前面操作完的字符串
					cnt+=last[j]-i;
          cnt+=j-last[j]-1;
					i=j-1;//直接让i=j-1，在外层循环会让i加2，效果是让i从j的下一个开始遍历
          //因为从当前i到当前j已经操作完了，所以可以直接改掉i
					break;
				}
			}
		}
	}
	if(!((s.size()-cnt)&1))cnt++;//最后剩下偶数个字符，再删一个
	write(cnt);
	return 0;
}

题目大意

给定一个仅含小写字母的字符串 $S$（$1 \le |S| \le 10^6$），定义一个字符串是"好的"，当且仅当：

1. 长度为奇数；
2. 对于任意偶数位（下标从 1 开始）的字符，都与它的下一个（奇数位）字符相同。

也就是说，好字符串一定长这样：

第 1 位是任意一个"自由字符"，之后是若干个"相邻且相同的字符对"首尾相接。

求最少删除多少个字符，可以使 $S$ 变成好字符串。

思路分析

1. 第一个字符必然可以白嫖

好字符串的第 1 位没有任何约束，可以是任意字符。所以我们固定保留原串的 s[0] ——这样做显然是合理的，毕竟他前面没有偶数位需要进行配对，而且题目天然要求需要一个单独的字符才能满足结果是奇数而且必须是在第一位。

于是问题转化为：从 s[1] 开始的后半部分，最少删多少字符，能使剩下的字符两两分组、每组内部相邻且相同（即变成若干个"AA"字符对首尾相连）。

2. 贪心：能配对就立刻配对

从 s[1] 开始扫描，维护一个 used[26] 标记当前"待配对字符"里已经出现过的字符：

• 若当前字符 c 还没出现过，标记它已出现，继续往后扫；
• 若当前字符 c 已经出现过，说明我们找到了当前查找的字符里最早能配成的一对相同字符：把 c 和它之前的那次出现直接拼在一起作为一个"AA"字符对，已经扫描过的其余字符（包括两次 c 之间夹着的字符）全部删除，然后清空数组，从下一个位置重新开始找下一对。

为什么"能配对就立刻配对，且选最早出现的重复"是最优的？

用交换论证说明：设当前扫描的字符从位置 $i$ 开始，第一次出现重复是在位置 $j$（即 $s_j$ 在 $[i, j-1]$ 中出现过，设那次出现位置为 $k$）。

• 若不在此时配对，而是把 $s_k$ 或 $s_j$ 留到更靠后的位置去和别的字符配对，那么原本 $[i, j]$ 这一段能够"仅删除 $j-i-1$ 个字符就凑出一对"的机会就被放弃了，最终要么要多删字符才能凑出别的对，要么根本凑不出，不会更优；
• 而且越早配对，剩给后面的字符区间越大、越自由，后续能够利用的配对机会只多不少。

因此"遇到重复立刻原地配对，数组清空重开"这一贪心策略是可以保证全局最优的。

3. 复杂度

由于字符集只有 26 个小写字母，每次最多扫 26 个不同字符就一定会触发一次重复（抽屉原理），所以整体是 $O(26n)$ 的线性做法，对于 $n = 10^6$ 完全可以接受。

实现

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

string str;
int n;
int used[256];
int niceLen = 1;   // s[0] 一定是要保留的

int main() {
    cin >> str;
    n = str.size();

    for (int i = 1; i < n; i++) {
        char c = str[i];
        if (used[c] == 0) {
            used[c] = 1;               // 窗口内首次出现，标记
        } else {
            niceLen += 2;           // 找到一对，保留这两个字符
            for (char ch = 'a'; ch <= 'z'; ch++)
                used[ch] = 0;          // 清空窗口，重新开始找下一对
        }
    }

    cout << n - niceLen;
    return 0;
}

样例验证

样例 1：aabaaba

• s[0] = 'a'，白嫖保留，niceLen = 1
• 从 i=1 开始扫：a（首次出现）→ b（首次）→ a（重复！配对，niceLen = 3，清空记录）
• 继续从 i=4 开始：a（首次）→ b（首次）→ a（重复！配对，niceLen = 5，清空记录）
• 扫描结束，niceLen = 5，答案为 $7 - 5 = 2$，与样例输出一致。

总结

本题的核心是一个局部最优可以推出全局最优的贪心：固定首字符自由使用，之后每次只要发现数组内出现了重复字符，就立刻原地配对、清空重开。这样贪心的正确性可以用交换论证证明，实现上只需一个大小 26（或 256）的标记数组线性扫描即可，代码简洁、复杂度低、边界情况少，是本题比较推荐的写法。