字符串的最大/最小表示法_java字符串的最小表示法

1. 最大/最小表示定义

给出一个字符串,比如abcdefg 我们可以选择任意一个字符作为字符传的开始位置，比如选择a, 得到字符串abcdefg, 选择b得到bcdefga, 选择c得到cdefgab… 选择g得到gabcdefg, 其中的最大表示即位字典序最大的一个选择: gabcdefg, 最小表示积为字典序最小的一个选择: abcdefg

---

2. 暴力法求解

// 最小表示法
 public static String minPresentStr(String s){
         int i = 0, j = 1, k = 0, n = s.length();//i j初始指向两个可能的位置
            while (i < n && j < n && k < n) {
                if (s.charAt((i + k) % n) == s.charAt((j + k) % n)) {//1.
                    k++;//遇到的字符一样 继续查找
                } else {
                    if (s.charAt((i + k) % n) > s.charAt((j + k) % n)) {
                        i = i+1;//s[i+k]>s[j+k]  以s[i]开头的字符串字典序一定大于s[j]开头的字符串的字典序 i往后移动一个位置 期待找到更小的s[i]<s[j]
                    } else if (s.charAt((i + k) % n) < s.charAt((j + k) % n)) {
                        j = j + 1;//s[i+k]<s[j+k]  以s[j]开头的字符串字典序一定大于s[i]开头的字符串的字典序 j往后移动一个位置 期待找到更小的s[j]<s[i]
                    }
                    if (i == j) {//相等时往后移动i或j一个位置 不移动的话会导致1处的if一直成立 这样就找不出答案了
                        i++;
                    }
                    k = 0;
                }

            }
            int start = Math.min(i, j);//最后结果取i  j中的最小值
            return s.substring(start, n) + s.substring(0, start);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 最大表示法
 public static String maxPresentStr(String s){
         int i = 0, j = 1, k = 0, n = s.length();
            while (i < n && j < n && k < n) {
                if (s.charAt((i + k) % n) == s.charAt((j + k) % n)) {
                    k++;
                } else {
                    if (s.charAt((i + k) % n) > s.charAt((j + k) % n)) {
                        j = j+1;
                    } else if (s.charAt((i + k) % n) < s.charAt((j + k) % n)) {
                        i = i + 1;
                    }
                    if (i == j) {
                        i++;
                    }
                    k = 0;
                }

            }
            int start = Math.min(i, j);
            return s.substring(start, n) + s.substring(0, start);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

每次比较i和j开始的循环同构，把当前比较到的位置记作 ，每次遇到不一样的字符时便把大的/小的跳过，最后剩下的就是最优解

对于aaaaab这种特殊的字符串 , 不难发现这个算法的复杂度退化为$O(n^2)$ 。

---

3. 优化求解

假设以位置i开始的字符串为s[i,i+k] 以位置j开始的字符串为s[j,j+k] 这两个字符串的长度为k+1, 假设这两个字符串的前k个字符相同，即s[i:i+k-1]==s[j:j+k-1] 只有最后一个字符s[i+k]!=s[j+k]

假设s[i+k]>s[j+k]:
那么以i~i+k范围内的任意一个位置作为开始位置形成的字符串，都会有一个以j~j+k位置开始的字符串，后者的字典序更小
原因： 如果以s[i+k]开始，那么以s[j+k]一定更优， 如果以s[i+p]开始($0<=p<=k-1$), 那么一定有s[i+q]($0<=q<=k-1$)更优，可以挑选s[j+q]使得s[j+q]=s[i+p], 这样s[i+p:i+k-1]=s[j+q:j+k-1](前k个字符相同是前提条件), 但是s[i+p]开始的字符串会保含s[i+k], s[j+q]开始的字符串会保含s[[j+k], 这样前面一样，最后一个字符后者的字典序较小，因此后者的字符串整体字典序较小

根据上面的讨论，当s[i+k]>s[j+k]时，暴力法中时将i往后移动一个位置，实际上可以将i往后移动k+1个位置，这就是优化所在

//优化后的最小表示法
public static String minPresenrStr(String s){
         int i = 0, j = 1, k = 0, n = s.length();
            while (i < n && j < n && k < n) {
                if (s.charAt((i + k) % n) == s.charAt((j + k) % n)) {
                    k++;
                } else {
                    if (s.charAt((i + k) % n) > s.charAt((j + k) % n)) {
                        i = i + k + 1;
                    } else if (s.charAt((i + k) % n) < s.charAt((j + k) % n)) {
                        j = j + k + 1;
                    }
                    if (i == j) {
                        i++;
                    }
                    k = 0;
                }

            }
            int start = Math.min(i, j);
            return s.substring(start, n) + s.substring(0, start);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//优化后的最大表示法
public static String maxPresenrStr(String s){
         int i = 0, j = 1, k = 0, n = s.length();
            while (i < n && j < n && k < n) {
                if (s.charAt((i + k) % n) == s.charAt((j + k) % n)) {
                    k++;
                } else {
                    if (s.charAt((i + k) % n) > s.charAt((j + k) % n)) {
                        j = j + k + 1;
                    } else if (s.charAt((i + k) % n) < s.charAt((j + k) % n)) {
                        i = i + k + 1;
                    }
                    if (i == j) {
                        i++;
                    }
                    k = 0;
                }

            }
            int start = Math.min(i, j);
            return s.substring(start, n) + s.substring(0, start);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22