K 距离间隔重排字符串。
给你一个非空的字符串 s 和一个整数 k，你要将这个字符串中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离至少为 k。
所有输入的字符串都由小写字母组成，如果找不到距离至少为 k 的重排结果，请返回一个空字符串 “”。
输入: s = “aabbcc”, k = 3。
输出: “abcabc” 。
解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。
力扣358。
时间紧。具体见代码。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
ret := rearrangeString("aabbcc", 3)
fmt.Println(ret)
}
func rearrangeString(s string, k int) string {
if len(s) < k {
return s
}
str := []byte(s)
cnts := make([][]int, 256)
for i := 0; i < 256; i++ {
cnts[i] = []int{i, 0}
}
maxCount := 0
for _, task := range str {
cnts[task][1]++
maxCount = getMax(maxCount, cnts[task][1])
}
maxKinds := 0
for task := 0; task < 256; task++ {
if cnts[task][1] == maxCount {
maxKinds++
}
}
N := len(str)
if !isValid(N, k, maxCount, maxKinds) {
return ""
}
ans := make([]string, 0)
for i := 0; i < maxCount; i++ {
ans = append(ans, "")
}
sort.Slice(cnts, func(i, j int) bool {
return cnts[j][1] <= cnts[i][1]
})
i := 0
for ; i < 256 && cnts[i][1] == maxCount; i++ {
for j := 0; j < maxCount; j++ {
ans[j] += fmt.Sprintf("%c", cnts[i][0])
}
}
out := 0
for ; i < 256; i++ {
for j := 0; j < cnts[i][1]; j++ {
ans[out] += fmt.Sprintf("%c", cnts[i][0])
out = twoSelectOne(out == len(ans)-2, 0, out+1)
}
}
builder := ""
for _, b := range ans {
builder += b
}
return builder
}
func isValid(N, k, maxCount, maxKinds int) bool {
restTasks := N - maxKinds
spaces := k * (maxCount - 1)
return spaces-restTasks <= 0
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}执行结果如下：
