Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.
All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".
Example 1:
s = "aabbcc", k = 3
Result: "abcabc"
The same letters are at least distance 3 from each other.
Example 2:
s = "aaabc", k = 3
Answer: ""
It is not possible to rearrange the string.
Example 3:
s = "aaadbbcc", k = 2
Answer: "abacabcd"
Another possible answer is: "abcabcda"
The same letters are at least distance 2 from each other.
一刷
題解：
首先構(gòu)造兩個(gè)array, 一個(gè)是長(zhǎng)度為26的frequency array, 一個(gè)是長(zhǎng)度為26的valid array, 記錄下一個(gè)相同字符至少需要出現(xiàn)在哪個(gè)位置。
每次尋找一個(gè)freq最大的并且滿(mǎn)足valid位置要求的字符混蔼。
public class Solution {
public String rearrangeString(String str, int k) {
int length = str.length();
int[] count = new int[26];
int[] valid = new int[26];
for(int i=0;i<length;i++){
count[str.charAt(i)-'a']++;
}
StringBuilder sb = new StringBuilder();
for(int index = 0;index<length;index++){
int candidatePos = findValidMax(count, valid, index);
if( candidatePos == -1) return "";
count[candidatePos]--;
valid[candidatePos] = index+k;
sb.append((char)('a'+candidatePos));
}
return sb.toString();
}
private int findValidMax(int[] count, int[] valid, int index){
int max = Integer.MIN_VALUE;
int candidatePos = -1;
for(int i=0;i<count.length;i++){
if(count[i]>0 && count[i]>max && index>=valid[i]){
max = count[i];
candidatePos = i;
}
}
return candidatePos;
}
}
