题目描述

小红定义一个字符串为"好串"， 当且仅当相令两个字母不相同。小红拿到了一个仅由工、'e' 'd"三种字符组成的字符串，她有个魔法:将相邻两个相同的字母同时删除，并在其位置生成任意一个字母(r 'e'、'd"= 种中的种)。例如，对于字符串"dedd",小红可以选择中间两个相邻字母"dd",将其变成"r"，此时字符串变为"der"。小红希望将给定的字符串变成好串"，她想知道自己最少需要多少次操作?

输入描述:

一个长度不超过200000的、仅由'r'、'e'、'd'三种字符组成的字符串。

输出描述:

一个整数，代表操作的最小次数。

示例一

输入：

rrdd

输出：

2

代码

public class Main {

    public static class Info {
        public int maxGood;
        public int minCost;

        public Info(int a, int b) {
            maxGood = a;
            minCost = b;
        }
    }

    public static Info process(int[] arr, int index, int prepre, int pre) {
        if (index == arr.length) {
            return new Info(0, 0);
        }
        // 前两个数都相同
        int bestValue = 0;
        int minCost = Integer.MAX_VALUE;

        // 三数相等
        if (prepre == pre && pre == arr[index]) {
            for (int i = 0; i <= 2; i++) {
                if (i == pre) continue; // 可以变成剩下两种
                Info info = process(arr, index + 1, pre, i);
                info.minCost += 1; // 自身需要变一次
                if (info.minCost < minCost) {
                    minCost = info.minCost;
                    bestValue = info.maxGood;
                }
            }
        } else if (pre == arr[index]) { // 两数相等
            for (int i = 0; i <= 2; i++) {
                if (i == pre || i == prepre) continue; // 只有一种选择
                Info info = process(arr, index + 1, pre, i);
                info.minCost += 1; // 自身需要变一次
                if (info.minCost < minCost) {
                    minCost = info.minCost;
                    bestValue = info.maxGood;
                }
            }
        } else { // 不和前面的相等
            Info info = process(arr, index + 1, pre, arr[index]);
            if (info.minCost < minCost) {
                minCost = info.minCost;
                bestValue = info.maxGood;
            }
        }
        return new Info(bestValue, minCost);
    }

    private static int solution(String str) {
        int n = str.length();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            char cur = str.charAt(i);
            if (cur == 'd') {
                arr[i] = 0;
            } else if (cur == 'e') {
                arr[i] = 1;
            } else {
                arr[i] = 2;
            }
        }
        int maxGood = 0;
        int minCost = Integer.MAX_VALUE;
        for (int prepre = 0; prepre < 3; prepre++) {
            for (int pre = 0; pre < 3; pre++) {
                if (pre == prepre) continue;
                // 0位置变换
                int cost = (arr[0] == prepre) ? 0 : 1;
                // 1位置变换
                cost += (arr[1] == pre) ? 0 : 1;
                // 去2位置做选择
                Info cur = process(arr, 2, prepre, pre);
                if (cur.maxGood > maxGood) {
                    maxGood = cur.maxGood;
                    minCost = cur.minCost + cost;
                } else if (cur.maxGood == maxGood) {
                    minCost = Math.min(minCost, cur.minCost + cost);
                }
            }
        }
        return minCost;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(
                new FileInputStream("data.txt")
        ));
        String str = br.readLine().trim();

        System.out.println(solution(str));
    }
}