2022-01-24：K 距离间隔重排字符串。给你一个非空的字符

原创

福大大架构师每日一题

发布于 2022-01-24 15:05:47

2460

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-01-24：K 距离间隔重排字符串。

给你一个非空的字符串 s 和一个整数 k，你要将这个字符串中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离至少为 k。

所有输入的字符串都由小写字母组成，如果找不到距离至少为 k 的重排结果，请返回一个空字符串 ""。

输入: s = "aabbcc", k = 3。

输出: "abcabc" 。

解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。

力扣358。

答案2022-01-24：

时间紧。具体见代码。

代码用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
    }
}