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:
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.
Compare each letter at same position of them. If s[i+k]<s[j+k]< code>, <span class="math inline">\(k\in(0,n)\)</span>, them string <span class="math inline">\(S_j\)</span> must bigger than string <span class="math inline">\(S_i\)</span>. For example:<br><code>s="aaabc", i=0, j=1</code>:</s[j+k]<>
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 withi=0: "aaabc"is smaller than (S_j)"aabca"which is start withj=1.
So string (S_j) j=1 must not be the answer. Then we should j 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]
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);
}
}
Original: https://www.cnblogs.com/liuzhch1/p/16555486.html
Author: liuzhch1
Title: LeetCode 899.有序队列｜字符串最小表示法的使用｜求循环字符串的最小值
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/606692/
转载文章受原作者版权保护。转载请注明原作者出处！