LeetCode 899.有序队列｜字符串最小表示法的使用｜求循环字符串的最小值

原题：899.Orderly Queue

Tags: #String

For a string s, each time you can choose one of first k letters and put it the end of string s. What is the lexicographically smallest string you can obtain?

Example1:

Input: s="dbbca", k=1
Output: s="adbbc"
Explanation:
Continuously put the first letter to end of s till 'a' is the first letter.

Example2:

Input: s="baaca", k=3
Output: s="aaabc"
Explanation:
First move: 'b' to end, now s="aacab"
Second move: 'c' to end, now s="aaabc"

Let’s divide this problem into two situations:

1. k>1
2. k=1

k>1(Simple)

Let’s consider k=2, we can move either the first letter or second letter to the end. If we move the second letter to the end, that is equal to move the letter advance one space in the string cycle: "bacc", move "a", then the string becomes "bcca", which is equal to “abcc“(just cycle 3 times). So that means we can move any character to any where in the string. Then we can always obtain a sorted lexicographically smallest string.
Any other case where k>2 is also the same.

    // if k>1
    char[] arr=s.toCharArray();
    Arrays.sort(arr);
    return String.valueOf(arr);

k=1(Interesting)

Each time we can only move one character to string end. That is Cyclic isomorphism(循环同构):

/[S_i=S[i,n]+S[0,i]=T
/]

/(S/) and /(T/) are called cyclic isomorphism.
To find the smallest cyclic isomorphism, we just need to index where the answer string starts in the string s. So we need to compare those n=s.length() strings.
Choose the i=0, j=1 as two strings’ beginning, compare them.

how to compare two string efficiently?

Compare each letter at same position of them. If s[i+k]<s[j+k], /(k/in(0,n)/), them string /(S_j/) must bigger than string /(S_i/). For example:
s="aaabc", i=0, j=1:

• k=0,1, s[i+k]=s[j+k]='a'
• k=2, s[i+k]='a' < s[j+k]='b', so string /(S_i/) start with i=0: "aaabc" is smaller than /(S_j/) "aabca" which is start with j=1.

So string /(S_j/) j=1 must not be the answer. Then we should j start next?

where to start next?

Consider string /(A/) and /(B/), they are /(S_i/) and /(S_j/) of string s, which means they start at /(i/) and /(j/). The first /(k/) letters of them are equal:

/[S[i,i+k-1]=S[j,j+k-1]
/]

W.o.l.g, consider /(S[i+k]<S[j+k]/), then all string /(S_{j+m}/) where /(0/leq m/leq k/) can’t be the answer. If /(S_{j+m}/) is the smallest answer, then /(S_{i+m}/) can be even smaller, cause /(S[i+k]<S[j+k]/).
So next j should be /(j+k+1/).

complexity?

We only need to go through the string one time(till the bigger one of i or j reach the end). So the time complexity is /(O(n)/), that’s quick!

Code:

public String orderlyQueue(String s, int m) {
    if (m == 1) {
        int i = 0, j = 1, k = 0, n = s.length();
        while (i < n && j < n && k < n) {
            char iCh = s.charAt((i + k) % n), jCh = s.charAt((j + k) % n);
            if (iCh == jCh)
                k++;
            else {
                if (iCh > jCh) {
                    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 {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        return String.valueOf(arr);
    }
}

Reference:
OI Wiki-最小表示法
宫水三叶的题解