陷入Java面试中，需要一些提示

Question

这是我坚持的面试问题：

给定一个由a，b和c组成的字符串，我们可以执行以下操作：取任意两个相邻的不同字符并将其替换为第三个字符。例如，如果“ a”和“
c”相邻，则可以将其替换为“ b”。重复应用此操作可能导致的最小字符串是多少？

我尝试的解决方案：

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        try {
            BufferedReader in = new BufferedReader(new InputStreamReader(
                    System.in));

            System.out.println(solve(in.readLine()));

            in.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static int solve(String testCase) {
        LinkedList<String> temp = new LinkedList<String>(deconstruct(testCase));

        for (int i = 0; i < (temp.size() - 1); i++) {
            if (!temp.get(i).equals(temp.get(i + 1))) {
                temp.add(i, getThirdChar(temp.remove(), temp.remove()));
                i = -1;
            }
        }

        return reconstruct(temp).length();
    }

    private static List<String> deconstruct(String testCase) {
        List<String> temp = new LinkedList<String>();

        for (int i = 0; i < testCase.length(); i++) {
            temp.add(testCase.charAt(i) + "");
        }

        return temp;
    }

    private static String reconstruct(List<String> temp) {
        String testCase = "";

        for (int i = 0; i < temp.size(); i++) {
            testCase += temp.get(i);
        }

        return testCase;
    }

    private static String getThirdChar(String firstChar, String secondChar) {
        return "abc".replaceAll("[" + firstChar + secondChar + "]+", "");
    }
}

该代码似乎可以在测试输入“ cab”（打印“ 2”），“ bcab”（打印“ 1”）和“ ccccc”（打印“
5”）上正常工作。但是我一直被告知我的代码是错误的。谁能帮助我找出错误所在？

Answer 1

正如人们已经指出的那样，错误是您的算法以预定义的顺序进行替换。您的算法将进行转换：

abcc --> ccc 代替 abcc --> aac --> ab --> c

如果要使用生成精简字符串的技术，则需要：

• 以所有可以想象的顺序（而不是仅一个预定义的迭代顺序）在一个级别上执行替换
• 找到一种明智的方法来确定哪种替换将最终产生最短的字符串

如果您只需要缩略字符串的长度，那么可以使用一种更简单的实现，它不需要生成缩略字符串。这是@Matteo答案的扩展版本，具有更多详细信息和有效的（非常简单的）算法。

简单属性

我假设在给定的规则集下，关于abc字符串，以下三个属性是正确的。

1. 如果无法进一步缩小字符串，则该字符串中的所有字符必须为同一字符。

2. 不可能：2 < answer < string.length是真的

3. 在执行归约运算时，如果运算前每个字母的计数为偶数，则运算后每个字母的计数将为奇数。相反，如果在操作之前每个字母的计数为奇数，则在操作之后的计数将为偶数。

物业1

属性一是微不足道的。

属性2（示例说明）

假设：我们有一个长度为5的精简串，以后再也不能精简。

AAAAA

由于此字符串是归约运算的结果，因此前一个字符串必须包含one B和one C。以下是可能的“父字符串”的一些示例：

BCAAAA，AABCAA，AAACBA

对于所有可能的父字符串，我们可以很容易地看到C：s和B：s中的至少一个可以与A：s而不是彼此组合。这将导致长度为5的字符串，该字符串将进一步减少。因此，我们已经说明了我们拥有不可约的长度为5的字符串的唯一原因是，我们在执行归约运算时没有正确选择要合并的字符。

这种推理适用于所有长度为k的简化字符串2 < k < string.length。

属性3（示例说明）

例如[numA, numB, numC] = [even, even, even]，如果有一个折减运算，我们用AB用AB代替AB。A和B的计数将减少1，使计数为奇数，而C的计数将增加1，使计数为奇数。好。

与此类似，如果两个计数为偶数且一个为奇数，则两个计数将为奇数，而在操作后甚至为一个，反之亦然。

换句话说，如果所有三个计数都具有相同的“均匀度”，那么任何减法运算都不能改变它。并且，如果计数的“均匀性”存在差异，则任何减法运算都无法更改该数值。

从属性得出结论

考虑两个不可约的字符串：

A 和 AA

对于A通知，[numA, numB, numC] = [odd, even, even] 对于AA通知，[numA, numB, numC] = [even, even, even]

现在忘记这两个字符串，并假设我们得到了长度为n的输入字符串。

如果字符串中的所有字符都相等，则答案显然是string.length。

另外，我们从属性2知道可以将字符串缩小到小于3的长度。我们还知道对执行缩小操作的均匀性的影响。如果输入的字符串包含所有字母或所有字母的奇计甚至数，也不可能将其降低到一个字母串，因为它是不可能均匀性结构改变，从[even, even, even]以[odd, even, even]通过执行还原操作。

因此，一个更简单的算法如下：

算法

Count the number of occurences of each letter in the input string [numA, numB, numC]

If two of these counts are 0, then return string.length

Else if (all counts are even) or (all counts are odd), then return 2

Else, then return 1