消除字符串，求最短字符串长度

Question

实现消消乐，消除一个字符串中连续相同且长度大于等于3的子字符串，求消除后的字符串最短长度。我已经实现了基本的消消乐，但无法实现最短字符串，就是举个例子，对于三个a+三个b+一个a（字符串），我只能先消去三个a，然后三个b，剩下一个a，但是题目要求最短，所以应该是先消去三个b，然后再消去剩下的连续四个a，长度最短为0，应该怎么办？（最好能使用栈解决）

Answer 1

参考gpt：
要实现最短字符串长度，你可以使用递归或者循环的方式来进行多次消除，直到无法再进行消除为止。下面是一个使用递归的示例代码，可以帮助你理解该思路：

public class StringElimination {
    public static void main(String[] args) {
        String input = "aaabbbba";
        int shortestLength = getShortestLength(input);
        System.out.println("Shortest Length: " + shortestLength);
    }

    public static int getShortestLength(String str) {
        if (str == null || str.length() < 3) {
            return str.length();
        }

        StringBuilder sb = new StringBuilder(str);
        int shortestLength = sb.length();

        for (int i = 0; i < sb.length() - 2; i++) {
            if (sb.charAt(i) == sb.charAt(i + 1) && sb.charAt(i) == sb.charAt(i + 2)) {
                int j = i + 3;
                while (j < sb.length() && sb.charAt(j) == sb.charAt(i)) {
                    j++;
                }

                sb.delete(i, j);
                int lengthAfterElimination = getShortestLength(sb.toString());

                if (lengthAfterElimination < shortestLength) {
                    shortestLength = lengthAfterElimination;
                }

                sb.insert(i, str.substring(i, j - (j - i - 3))); // 还原已删除的子字符串
            }
        }

        return shortestLength;
    }
}

在上述代码中，我们使用递归的方式进行消除操作。首先，遍历字符串中的每个字符，判断是否连续出现了三次及以上。如果是，就删除这个连续子字符串，并递归调用 getShortestLength 方法来计算删除后的字符串的最短长度。然后，将删除的子字符串还原回原始字符串，继续遍历下一个字符。最后返回最短长度。