string - 文字列削減

Question

今ではよく知られている問題かもしれません.3文字（a、b、c）のみを含む文字列 S を考えてみてください。これらの文字列に対してこのリダクション操作を実行できます。「'ab' は 'c' に、'ac' は 'b' に置き換えることができます。」この手術でどれだけ減らせるか？

答えは常に (1,2,string.length) です。

string.length すべての文字が同じ場合は 2、S の count(a) = count(b) = count(c) の場合。しかし、私はそれを証明することができません。

どんな提案も本当に役に立ちます。

Answer 1

Sの長さに関する帰納法によって、このタイプの主張を証明します。

しかし、あなたは正しい主張をしなければなりません、そしてあなたはここにいません。あなたの主張は

答えは | さ| すべての文字が同じ場合、 Sでcount(a) = count(b) = count(c) の場合は 2、それ以外の場合は 1。

文字列を考えてみましょうaabb。あなたの主張は、これは長さ 1 に縮小できると言っていますが、実際には長さ 2 にしか縮小できません。可能な縮小シーケンスはaabb→ acb→bbとaabb→ acb→aaです。

主張を正しく行えば、証拠を完成させることができるはずです。