2023-05-21：给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。返回在应用上述步骤的任意数量的移动后，字典上最小的字符串。输入：s

作者：福大大架构师每日一题

2023-05-21
北京
本文字数：2746 字
阅读完需：约 9 分钟

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)}