刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorganize-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"

示例 2:

输入: S = "aaab"
输出: ""

注意:
S 只包含小写字母并且长度在[1, 500]区间内。

思路

本题有两块内容需要思考，一个是如何判断能否得到相邻字符不同的字符串；一个是如何得到这样的字符串
通过一些常识，不难想到，如果字符串中最多的一个字符不大于n+1/2，则就存在这样的一个字符串
这块相对简单
剩下的就是如何得到一个这样的字符串了
首先考虑下极限情况，如果只有一个字符串或者空字符串，则直接返回
如果一共奇数长，有n+1/2个相同的字符，则一定是偶数位置全部摆放最多的这个字符才会得到相邻字符不同的字符串，如果一共偶数长，n/2的最多字符可以在奇数位，也可以在偶数位，那么我们就划分出奇数位和偶数位，间隔插入相同字符即可得到一个这样的字符串。贪心思路

代码

func reorganizeStringMY(S string) string {
    n := len(S)
    if n <= 1 {
        return S
    }

    cnt := [26]int{}
    maxC := 0
    for _, c := range S {
        c -= 'a'
        cnt[c] += 1
        if cnt[c] > maxC {
            maxC = cnt[c]
        }
    }

    if maxC > (n + 1) / 2 {
        return ""
    }

    // 输出
    ret := make([]byte, n)
    oddP, evenP, halfLen := 1, 0, n/2
    for k, v := range cnt {
        // 分奇数位 和 偶数位输出
        c := byte('a' + k)
        for v > 0 && v <= halfLen && oddP < n {
            ret[oddP] = c
            v --
            oddP += 2
        }
        for v > 0 && evenP < n {
            ret[evenP] = c
            v --
            evenP += 2
        }
    }
    return string(ret)
}

此致，共勉