문자열 감소

Question

는 지금까지 잘 알려진 문제입니다 수 있음. 이 문자열에 대해 다음과 같은 축소 작업을 수행 할 수 있습니다. "세 번째 문자로 'ab'가 'c'로, 'ac'가 'b'로 대체 될 수 있습니다." 이 작업으로 얼마나 줄일 수 있습니까?

답변은 항상 (1,2, string.length)입니다.

string.length 모든 문자가 동일하면 2 iff count (a) = count (b) = count (c) 그렇지 않으면 그러나 나는 그것을 증명할 수 없다.

어떤 제안이라도 도움이 될 것입니다.

Answer 1

당신은 의 길이 S에 유도에 의해 주장의 유형을 증명한다.

하지만 권리를 주장해야하며 여기에 있지 않습니다. | 귀하의 주장은 답이

입니다 S | 모든 문자가 같으면 S에 count (a) = count (b) = count (c)이면 2이고 그렇지 않으면 1입니다.

문자열 aabb을 고려하십시오. 귀하의 주장에 따르면 길이 1로 줄일 수 있지만 길이 2로만 줄일 수 있습니다. 가능한 감소 순서는 aabb → acb → bb 및 aabb → acb → aa입니다.

권리를 주장하십시오. 증명을 완료 할 수 있어야합니다.