最小表示法

• OI Wiki: https://oi-wiki.org/string/minimal-string/

题目	难度
899. 有序队列	困难

定义

循环同构

当字符串 S 中可以选定一个位置 i 满足 S[i,n] + S[1,i-1] = T。

则称 S 与 T 循环同构。

最小表示

字符串 S 的最小表示为与 S 循环同构的所有字符串中字典序最小的字符串。

899. 有序队列

import java.util.Arrays;

public class Solution899 {
    public String orderlyQueue(String s, int _k) {
        int n = s.length();
        char[] chars = s.toCharArray();
        if (_k == 1) {
            // 最小表示法
            // https://oi-wiki.org/string/minimal-string/
            int k = 0;
            int i = 0;
            int j = 1;
            while (k < n && i < n && j < n) {
                if (chars[(i + k) % n] == chars[(j + k) % n]) {
                    k++;
                } else {
                    if (chars[(i + k) % n] > chars[(j + k) % n]) {
                        i = i + k + 1;
                    } else {
                        j = j + k + 1;
                    }
                    if (i == j) {
                        i++;
                    }
                    k = 0;
                }
            }
            i = Math.min(i, j);
            return s.substring(i) + s.substring(0, i);
        } else {
            Arrays.sort(chars);
            return new String(chars);
        }
    }
}

（全文完）