一、概念
最小表示法是用于解决字符串最小表示问题的方法。
循环同构：
当字符串 S 中可以选定一个位置 i 满足
S[i⋅⋅⋅n]+S[1⋅⋅⋅i−1]=T
则称 S 与 T 循环同构
最小表示：
字符串 S 的最小表示为与 S 循环同构的所有字符串中字典序最小的字符串
算法流程：
- 初始化指针 i 为 0，j 为 1；初始化匹配长度 k 为 0
- 比较第 k 位的大小，根据比较结果跳转相应指针。若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同
- 重复上述过程，直到比较结束
- 答案为 i, j 中较小的一个
时间复杂度：O(N)
二、模板
int i = 0, j = 1, k = 0, n = s.length();
while(i < n && j < n && k < n) {
int a = chars[(i + k) % n], b = chars[(j + k) % n];
if(a == b) k ++;
else {
if(a > b) i += k + 1; else j += k + 1;
if(i == j) i ++;
k = 0;
}
}
i = Math.min(i, j);三、例题
题：899. 有序队列
给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。
示例 1：
输入：s = "cba", k = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。示例 2：
输入：s = "baaca", k = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。
提示：
1 <= k <= S.length <= 1000
s 只由小写字母组成。解：
- 当 k > 1时，我们可以构造出任意的字符方案，所以可直接通过排序得到答案。
- 当 k = 1时，我们共有n种候选方案（将字符串看作一个首尾相接的循环字符串，共有n个起点可枚举）
解题思路：模拟
AC代码：
class Solution {
public String orderlyQueue(String s, int k) {
if(k == 1) {
StringBuilder sb = new StringBuilder(s);
for(int i = 1; i < s.length(); ++ i) {
sb.append(sb.charAt(0)).deleteCharAt(0);
if(sb.toString().compareTo(s) < 0) {
s = sb.toString();
}
}
return s;
} else {
char[] chars = s.toCharArray();
Arrays.sort(chars);
return String.valueOf(chars);
}
}
}解题思路：最小表示法
AC代码：
class Solution {
public String orderlyQueue(String s, int _k) {
char[] chars = s.toCharArray();
if(_k == 1) {
int i = 0, j = 1, k = 0, n = s.length();
while(i < n && j < n && k < n) {
int a = chars[(i + k) % n], b = chars[(j + k) % n];
if(a == b) k ++;
else {
if(a > b) i += k + 1; else 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 String.valueOf(chars);
}
}
}
