鴿籠原理解Leetcode 767. Reorganize String

 

3隻狗4狗洞每隻狗都有一個狗洞，但只有兩個狗洞就不可能。若某個字元 c 的頻率 freq(c) 大於 (n+1)/2，根據鴿籠原理(Pigeonhole principle)，找到一個相鄰字元不相同的字串是不可能的，反之則可能。當有 4 個成一排的狗洞，而有 3 隻狗時，不可能存在相鄰的狗洞讓這 3 隻狗分開，5個狗洞就可以。

若 n 是奇數，兩端都要，可以有最多 (n+1)/2 個交替位置。若 n 是偶數，最多有 n/2 個交替位置。

若某個字元 c 的頻率 freq(c) 大於 (n+1)/2，則必然存在相同字元 c 的相鄰位置

[codes]https://leetcode.com/problems/reorganize-string/solutions/3947847/c-frequency-tables-put-chars-alternating-indices-beats-100/