string - 字符串缩减

Question

现在可能这是一个众所周知的问题：考虑任何字符串 S ，仅包含 3 个字符 (a,b,c)。您可以对这些字符串执行此缩减操作：“将两个连续的不同字符替换为第三个字符，例如 'ab' 可以替换为 'c' 和 'ac' cab 可以替换为 'b'。” 我们可以通过这个操作减少多少？

答案总是 (1,2,string.length) 。

string.length 如果所有字符都相同，则 2 iff count(a) = count(b) = count(c) 在 S. 1 中否则。但我无法证明这一点。

任何建议都会非常有帮助。

Answer 1

您通过对S的长度进行归纳来证明这种类型的声明。

但是您必须正确地提出索赔，而您还没有。你的主张是

答案是| 小号| 如果所有字符都相同，如果 count(a) = count(b) = count(c) 在S中为 2，否则为 1。

考虑字符串aabb。您的说法说这可以减少到长度 1，但实际上它只能减少到长度 2：可能的减少序列是aabb→ acb→bb和aabb→ acb→ aa。

获得正确的索赔，您应该能够完成证明。