最小（大）表示法

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

题目	难度
899. 有序队列	困难	最小
1163. 按字典序排在最后的子串	困难	最大
3403. 从盒子中找出字典序最大的字符串 I	中等	最大

定义

循环同构

当字符串 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) {
        char[] s = S.toCharArray();
        if (k == 1) {
            int i = minimalString(s, true);
            return S.substring(i) + S.substring(0, i);
        } else {
            Arrays.sort(s);
            return new String(s);
        }
    }

    // 最小表示法
    private int minimalString(char[] s, boolean isMin) {
        int n = s.length;
        int k = 0, i = 0, j = 1;
        while (k < n && i < n && j < n) {
            int d = chr(s, i + k, isMin) - chr(s, j + k, isMin);
            if (d == 0) {
                k++;
            } else {
                if (d > 0 == isMin) i = i + k + 1;
                else j = j + k + 1;
                if (i == j) i++;
                k = 0;
            }
        }
        i = Math.min(i, j);
        return i;
    }

    private int chr(char[] s, int i, boolean isMin) {
        int n = s.length;
        if (i >= n) return isMin ? s[i % n] : 0;
        return s[i];
    }
}

1163. 按字典序排在最后的子串

public class Solution1163 {
    public String lastSubstring(String s) {
        return s.substring(minimalString(s.toCharArray(), false));
    }

    // 最小表示法
    private int minimalString(char[] s, boolean isMin) {
        int n = s.length;
        int k = 0, i = 0, j = 1;
        while (k < n && i < n && j < n) {
            int d = chr(s, i + k, isMin) - chr(s, j + k, isMin);
            if (d == 0) {
                k++;
            } else {
                if (d > 0 == isMin) i = i + k + 1;
                else j = j + k + 1;
                if (i == j) i++;
                k = 0;
            }
        }
        i = Math.min(i, j);
        return i;
    }

    private int chr(char[] s, int i, boolean isMin) {
        int n = s.length;
        if (i >= n) return isMin ? s[i % n] : 0;
        return s[i];
    }
}

3403. 从盒子中找出字典序最大的字符串 I

public class Solution3403 {
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) return word;

        int n = word.length();
        // 取最大子串长度为 n - numFriends + 1 的前缀
        int i = minimalString(word.toCharArray(), false);
        int maxLen = Math.min(n + 1 - numFriends, n - i);
        return word.substring(i, i + maxLen);
    }

    // 最小表示法
    private int minimalString(char[] s, boolean isMin) {
        int n = s.length;
        int k = 0, i = 0, j = 1;
        while (k < n && i < n && j < n) {
            int d = chr(s, i + k, isMin) - chr(s, j + k, isMin);
            if (d == 0) {
                k++;
            } else {
                if (d > 0 == isMin) i = i + k + 1;
                else j = j + k + 1;
                if (i == j) i++;
                k = 0;
            }
        }
        i = Math.min(i, j);
        return i;
    }

    private int chr(char[] s, int i, boolean isMin) {
        int n = s.length;
        if (i >= n) return isMin ? s[i % n] : 0;
        return s[i];
    }
}

（全文完）