方法思路

1. 从左到右遍历字符串，尝试构建一个合法的字符串
2. 每次添加一个字符后，检查是否违反两个规则：
   • 三个连续相同字符 (如 "aaa")
   • 两对连续相同字符 (如 "aabb")
3. 如果违反规则，则删除最后添加的字符
4. 最终，原始字符串长度减去合法字符串长度即为需要删除的字符数

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        
        List<Character> list = new ArrayList<>();
        for (char c : str.toCharArray()) {
            list.add(c);
            int len = list.size();
            
            // 检查是否形成两对连续相同字符 (如 "aabb")
            if (len >= 4 && list.get(len - 1) == list.get(len - 2) && 
                list.get(len - 3) == list.get(len - 4)) {
                list.remove(len - 1);
                continue;
            }
            
            // 检查是否形成三个连续相同字符 (如 "aaa")
            if (len >= 3 && list.get(len - 1) == list.get(len - 2) && 
                list.get(len - 2) == list.get(len - 3)) {
                list.remove(len - 1);
            }
        }
        
        System.out.println(str.length() - list.size());
    }
}

Python

def min_deletions(s):
    result = []
    
    for c in s:
        result.append(c)
        length = len(result)
        
        # 检查是否形成两对连续相同字符 (如 "aabb")
        if (length >= 4 and result[length-1] == result[length-2] and 
            result[length-3] == result[length-4]):
            result.pop()
            continue
        
        # 检查是否形成三个连续相同字符 (如 "aaa")
        if (length >= 3 and result[length-1] == result[length-2] and 
            result[length-2] == result[length-3]):
            result.pop()
    
    return len(s) - len(result)

s = input().strip()
print(min_deletions(s))

C++

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

int main() {
    string str;
    cin >> str;
    
    vector<char> list;
    for (char c : str) {
        list.push_back(c);
        int len = list.size();
        
        // 检查是否形成两对连续相同字符 (如 "aabb")
        if (len >= 4 && list[len-1] == list[len-2] && 
            list[len-3] == list[len-4]) {
            list.pop_back();
            continue;
        }
        
        // 检查是否形成三个连续相同字符 (如 "aaa")
        if (len >= 3 && list[len-1] == list[len-2] && 
            list[len-2] == list[len-3]) {
            list.pop_back();
        }
    }
    
    cout << str.length() - list.size() << endl;
    return 0;
}