899. 有序队列

传送门

思路

这是一道看似 Hard，实则想出方法就 Easy 的题。
当 \(k = 1\) 时，变成找字典序最小的循环子串问题。
当 \(k > 1\) 时，经过任意步移动一定可以将字符串 \(S\) 变成升序字符串。

证明
当 \(k = 2\) 时，类比插入排序，可以假装将 \(S[0]\) 拿出，不停地将 \(S[1]\) 移动到字符串末尾，就好像字符串在旋转。转到合适的位置时，将 \(s[0]\) 插入字符串。经过若干次操作后，就能对字符串完成排序。

flowchart LR

0
1 --> n-1
n-1 --> n-2
n-2 -..-> 3
3 --> 2
2 --> 1

实现

function orderlyQueue(s: string, k: number): string {
    if(s.length === 1) {
        return s
    }
    if(k == 1) {
        let res: string = s
        for(let i = 0; i < s.length; ++i) {
            s = s.substring(1) + s[0]
            res = res < s ? res : s
        }
        return res
    }
    else {
        return Array.from(s).sort().join('')
    }
};

\(k = 1\) 时，时间复杂度为 \(O(n^2)\)，
\(k > 1\) 时，时间复杂度为 \(O(n \log n)\)

\(k = 1\) 情况的优化

\(k = 1\) 其实就是求字符串的最小表示，可以将时间复杂度优化到 \(O(n)\)。

function minimumRepresentation(s: string): number {
  let len: number = 0, i: number = 0, j: number = 1
  const n: number = s.length
  while (len < n && i < n && j < n) {
    const a: string = s[(i + len) % n]
    const b: string = s[(j + len) % n]
    if (a == b) {
      ++len
    } else {
      if (a > b) {
        i = i + len + 1
      }
      else {
        j = j + len + 1
      }
      len = 0
      if (i == j) {
        ++i
      }
    }
  }
  return Math.min(i, j)
}

function orderlyQueue(s: string, k: number): string {
    if(s.length === 1) {
        return s
    }
    if(k == 1) {
        const index = minimumRepresentation(s)
        return s.substring(index) + s.substring(0, index)
    }
    else {
        return [...s].sort().join('')
    }
}