字符串减少 [英] String reduction

问题描述

可能这是一个众所周知的问题现在：  考虑任何字符串S，只包含3个字符（A，B，C）。你可以这样做减少操作上的这些字符串：由第三人喜欢'AB'可以是'C'和'交流'的驾驶室是由B代替取代连续两个截然不同的角色。多少我们可以通过这种操作降低？

May be it's a well-known problem by now : consider any string S , containing only 3 characters (a,b,c). You can do this reduction operation on these strings : "replace two consecutive distinct characters by the 3rd one like 'ab' can be replace by 'c' and 'ac' cab be by 'b'." how much we can reduce by this operation?

，答案始终为（1,2，string.length减）。

the answer is always either (1,2,string.length) .

string.length减当且仅当所有字符都是一样的， 2当且仅当计数（一个）=计数（B）=计数（c）如S. 否则为1。 但我不能证明这一点。

string.length iff all characters are same, 2 iff count(a) = count(b) = count(c) in S. 1 otherwise. but i am not able to prove it .

任何建议将是很有益的。

Any suggestion will be really helpful.

推荐答案

您通过归纳证明这种主张对的取值的长度。

You prove this type of claim by induction on the length of S.

不过，你必须得到索赔的权利，而你不在这里。你的要求

But you have to get the claim right, and you haven't here. Your claim is

答案| 取值的|如果所有的字符都是一样的，2，如果count（A）= COUNT（B）=计（三）的取值的，否则为1。

the answer is |S| if all characters are same, 2 if count(a) = count(b) = count(c) in S, and 1 otherwise.

考虑字符串 AABB 。你的要求说，这可以减少到长度为1，但实际上它只能降低到长2：尽可能减少序列<​​code> AABB → ACB → BB 和 AABB → ACB $→ AA 。

Consider the string aabb. Your claim says that this can be reduced to length 1, but in fact it can only be reduced to length 2: the possible reduction sequences are aabb → acb → bb and aabb → acb → aa.

获取请求权，你应该能够完成的证明。

Get the claim right and you should be able to complete the proof.

这篇关于字符串减少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！