需求

给定一个字符串，检查是否可以重新排列字符串，使结果满足如下条件：

• 相邻的字符不相同

如果满足条件，则返回任意可行的结果，否则返回空字符串。 比如，给定字符串 "aab"，返回 "aba"。

思路

首先需要找到一种算法来不同都字符穿插排列。并非任何场景的输入都可以构成新的字符串，因此我们需要一种算法来检查是否可以构成新的字符串， 比如输入"aaaa"，则无论怎么排列，都无法满足题目都排列要求。 实际上，如果能够构成新的字符串，那么就必须满足如下条件：

maxCharCount < (stringLength + 1) / 2

其中，maxCharCount是次数出现最多的字符数量，stringLength是字符串的长度。

可以采用下面的思路来对字符串进行重排：

• 将原字符串中每个字符的个数分配统计出来.
• 将统计出来的结果按照字符的个数进行排序.
• 从数据源列表中依次取值填充到新的空列表中，填充空列表时，先将偶数位全部填充完成，再填充奇数位.
• 将列表重新组合成最终的结果字符串.

实现

package chapter02

import (
    "sort"
    "strings"
)

type Pair struct {
    Key   string
    Value int
}

type PairList []Pair

func (p PairList) Len() int           { return len(p) }
func (p PairList) Less(i, j int) bool { return p[i].Value < p[j].Value }
func (p PairList) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func reorganize(s string) string {

    var dic = make(map[string]int)
    for _, v := range s {
        s := string(v)
        dic[s]++
    }
    // 由于go没有map的排序，所以需要自己实现一个排序，内置sort包是以切片为基础的排序
    var pairList = make(PairList, 0)
    for k, v := range dic {
        p := Pair{k, v}
        pairList = append(pairList, p)
    }
    // 排序
    sort.Sort(pairList)
    if len(s) == 0 || pairList[len(pairList)-1].Value > (len(s)+1)/2 {
        return ""
    }
    //fmt.Printf("%v\n", pairList)

    // 当前要插入的字符
    var pair Pair

    // 开始执行奇偶插空
    var res = make([]string, len(s))
    for i := 0; i < len(s); i += 2 {
        if pair.Value == 0 {
            // 如果是Java或Python等有内置数组操作方法,可以使用pop()方法
            pair = pairList[len(pairList)-1]
            pairList = pairList[:len(pairList)-1]
        }
        res[i] = pair.Key
        pair.Value--
    }
    for i := 1; i < len(s); i += 2 {
        if pair.Value == 0 {
            pair = pairList[len(pairList)-1]
            pairList = pairList[:len(pairList)-1]
        }
        res[i] = pair.Key
        pair.Value--
    }
    return strings.Join(res, "")
}