2023-05-21：给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，

并把它加到字符串的末尾。

返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串。

输入：s = “baaca”, k = 3。

输出：”aaabc”。

答案2023-05-21：

大体过程如下：

1.当 k 大于 1 时，直接将字符串 s 中的字符按照字典序排序，得到排序后的字符串 s’，返回 s’。

2.当 k 等于 1 时，需要使用 DC3 算法对字符串 s 进行处理，得到其所有后缀排名，并找到排名最小的后缀起始位置 minRankIndex。

3.将字符串 s 的前 minRankIndex 个字符移动到字符串末尾，得到新的字符串 s’，返回 s’。

值得注意的是，DC3 算法是一种用于求解后缀数组的算法，可以在 O(n) 的复杂度内计算一个字符串的后缀数组。在本题中，我们需要用到 DC3 算法来寻找字符串 s 所有后缀的排名，以便找到排名最小的后缀起始位置。

对于给定字符串 s 和整数 k，orderlyQueue 函数的时间复杂度和空间复杂度分别如下：

1.当 k > 1 时，时间复杂度为 O(nlogn)，其中 n 是字符串 s 的长度。主要耗时在排序操作中，使用快速排序等算法可以达到 O(nlogn) 的复杂度。空间复杂度也为 O(nlogn)，主要用于存储字符串数组的副本和排序结果。

2.当 k = 1 时，时间复杂度为 O(n)，其中 n 是字符串 s 的长度。时间复杂度主要来自 DC3 算法的实现，该算法可以在 O(n) 的时间复杂度内计算一个字符串的后缀数组。空间复杂度为 O(n)，主要用于存储后缀数组、排名和其他中间变量。

综上所述，orderlyQueue 函数的时间复杂度为 O(nlogn) 或 O(n)，空间复杂度为 O(nlogn) 或 O(n)，具体取决于 k 的值。

go完整代码如下：

package main

import (
    "fmt"
    "sort"
    "strings"
)

func orderlyQueue(s string, k int) string {
    if k > 1 {
        sArr := strings.Split(s, "")
        sort.Strings(sArr)
        return strings.Join(sArr, "")
    } else {
        s2 := s + s
        n := len(s2)
        arr := make([]int, n)
        for i := 0; i < n; i++ {
            arr[i] = int(s2[i] - 'a' + 1)
        }
        dc3 := NewDC3(arr, 26)
        n = n >> 1
        minRankIndex := 0
        for i := 1; i < n; i++ {
            if dc3.rank[i] < dc3.rank[minRankIndex] {
                minRankIndex = i
            }
        }
        return s[minRankIndex:] + s[0:minRankIndex]
    }
}

// DC3算法实现
// 根据原算法Java代码修改
type DC3 struct {
    sa   []int
    rank []int
}

// NewDC3 构造函数
func NewDC3(nums []int, max int) *DC3 {
    dc3 := &DC3{}
    dc3.sa = dc3.sa0(nums, max)
    dc3.rank = dc3.rank0()
    return dc3
}

func (dc3 *DC3) sa0(nums []int, K int) []int {
    n := len(nums)
    arr := make([]int, n+3)
    copy(arr, nums)
    return dc3.skew(arr, n, K)
}

func (dc3 *DC3) skew(nums []int, n int, K int) []int {
    n0 := (n + 2) / 3
    n1 := (n + 1) / 3
    n2 := n / 3
    n02 := n0 + n2
    s12 := make([]int, n02+3)
    sa12 := make([]int, n02+3)
    for i, j := 0, 0; i < n+(n0-n1); i++ {
        if i%3 != 0 {
            s12[j] = i
            j++
        }
    }
    dc3.radixPass(nums, s12, sa12, 2, n02, K)
    dc3.radixPass(nums, sa12, s12, 1, n02, K)
    dc3.radixPass(nums, s12, sa12, 0, n02, K)

    name := 0
    c0 := -1
    c1 := -1
    c2 := -1
    for i := 0; i < n02; i++ {
        if nums[sa12[i]] != c0 || nums[sa12[i]+1] != c1 || nums[sa12[i]+2] != c2 {
            name++
            c0 = nums[sa12[i]]
            c1 = nums[sa12[i]+1]
            c2 = nums[sa12[i]+2]
        }
        if sa12[i]%3 == 1 {
            s12[sa12[i]/3] = name
        } else {
            s12[sa12[i]/3+n0] = name
        }
    }
    if name < n02 {
        sa12 = dc3.skew(s12, n02, name)
        for i := 0; i < n02; i++ {
            s12[sa12[i]] = i + 1
        }
    } else {
        for i := 0; i < n02; i++ {
            sa12[s12[i]-1] = i
        }
    }

    s0 := make([]int, n0)
    sa0 := make([]int, n0)
    for i, j := 0, 0; i < n02; i++ {
        if sa12[i] < n0 {
            s0[j] = 3 * sa12[i]
            j++
        }
    }
    dc3.radixPass(nums, s0, sa0, 0, n0, K)

    sa := make([]int, n)
    for p, t, k := 0, n0-n1, 0; k < n; k++ {
        i := sa12[t]
        if i < n0 {
            i = i*3 + 1
        } else {
            i = (i-n0)*3 + 2
        }
        j := sa0[p]
        if i < n-1 && j < n-1 {
            if nums[i] < nums[j] || (nums[i] == nums[j] && nums[i+1] < nums[j+1]) ||
                (nums[i] == nums[j] && nums[i+1] == nums[j+1] && nums[i+2] <= nums[j+2]) {
                sa[k] = i
                t++
                if t == n02 {
                    k++
                    for ; p < n0; p++ {
                        sa[k] = sa0[p]
                        k++
                    }
                }
            } else {
                sa[k] = j
                p++
                if p == n0 {
                    k++
                    for ; t < n02; t++ {
                        i := sa12[t]
                        if i < n0 {
                            sa[k] = i*3 + 1
                        } else {
                            sa[k] = (i-n0)*3 + 2
                        }
                        k++
                    }
                }
            }
        } else {
            if nums[i] < nums[j] || (nums[i] == nums[j] && nums[i+1] <= nums[j+1]) {
                sa[k] = i
                t++
                if t == n02 {
                    k++
                    for ; p < n0; p++ {
                        sa[k] = sa0[p]
                        k++
                    }
                }
            } else {
                sa[k] = j
                p++
                if p == n0 {
                    k++
                    for ; t < n02; t++ {
                        i := sa12[t]
                        if i < n0 {
                            sa[k] = i*3 + 1
                        } else {
                            sa[k] = (i-n0)*3 + 2
                        }
                        k++
                    }
                }
            }
        }
    }
    return sa
}

func (dc3 *DC3) radixPass(nums []int, input []int, output []int, offset int, n int, k int) {
    cnt := make([]int, k+1)
    for i := 0; i < n; i++ {
        cnt[nums[input[i]+offset]]++
    }
    for i, sum := 0, 0; i < len(cnt); i++ {
        t := cnt[i]
        cnt[i] = sum
        sum += t
    }
    for i := 0; i < n; i++ {
        output[cnt[nums[input[i]+offset]]] = input[i]
        cnt[nums[input[i]+offset]]++
    }
}

func (dc3 *DC3) rank0() []int {
    n := len(dc3.sa)
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        ans[dc3.sa[i]] = i
    }
    return ans
}

func main() {
    s := "baaca"
    k := 3
    result := orderlyQueue(s, k)
    fmt.Println(result)
}

本作品采用《CC 协议》，转载必须注明作者和本文链接