## Thursday, June 16, 2016

### LeetCode 358 - Rearrange String k Distance Apart

http://blog.csdn.net/jmspan/article/details/51678257
Given a non-empty string str 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:
```str = "aabbcc", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.
```
Example 2:
```str = "aaabc", k = 3

It is not possible to rearrange the string.
```
Example 3:
```str = "aaadbbcc", k = 2

The same letters are at least distance 2 from each other.```

X. Using Priority Queue
http://www.programcreek.com/2014/08/leetcode-rearrange-string-k-distance-apart-java/
```public String rearrangeString(String str, int k) {
if(k==0)
return str;

//initialize the counter for each character
final HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(map.containsKey(c)){
map.put(c, map.get(c)+1);
}else{
map.put(c, 1);
}
}

//sort the chars by frequency
PriorityQueue<Character> queue = new PriorityQueue<Character>(new Comparator<Character>(){
public int compare(Character c1, Character c2){
if(map.get(c2).intValue()!=map.get(c1).intValue()){
return map.get(c2)-map.get(c1);
}else{
return c1.compareTo(c2);
}
}
});

for(char c: map.keySet())
queue.offer(c);

StringBuilder sb = new StringBuilder();

int len = str.length();

while(!queue.isEmpty()){

int cnt = Math.min(k, len);
ArrayList<Character> temp = new ArrayList<Character>();

for(int i=0; i<cnt; i++){
if(queue.isEmpty())//\\
return "";

char c = queue.poll();
sb.append(String.valueOf(c));

map.put(c, map.get(c)-1);

if(map.get(c)>0){
}

len--;
}

for(char c: temp)
queue.offer(c);//\\
}

return sb.toString();
}```

for priorityqueue, if counts are same, you can compare the letter, so the order for polling out will be consistant.
https://discuss.leetcode.com/topic/49022/greedy-solution-beats-95
for example: "aaabbcc", k = 3
1. Count the statistics of letters, sort them in terms of frequency in a descending way.
so it has the result: a - 3, b - 2, c - 2.
1. Suppose the rewrite string length is len, divide the len into bins of size k, so in total
you have
bin number of nBin = (len - 1) / k + 1,
with last bin size:
lastBinSize = len % k.
in the example, nBin = 3, lastBinSize = 1;
1. Fill the same letter in different bins:
after filling 'a' ---> result = a##a##a
after filling 'b' ---> result = ab#ab#a
after filling 'c' ---> result = abcabca

http://dartmooryao.blogspot.com/2016/06/leetcode-358-rearrange-string-k.html
public String rearrangeString(String str, int k) {
if(k<=1){ return str; }
int[] count = new int[26];
for(int i=0; i<str.length(); i++){
count[str.charAt(i)-'a']++;
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->b[0]-a[0]);
for(int i=0; i<count.length; i++){ pq.add(new int[]{ count[i], i}); }

char[] result = new char[str.length()];
int idx = 0;
int start = 0;
while(!pq.isEmpty()){
int[] num = pq.remove();
for(int i=0; i<num[0]; i++){
result[idx] = (char)(num[1]+'a');
if(idx>0 && result[idx-1]==result[idx]){ return ""; }
idx+=k;
if(idx>=str.length()){ idx=++start; }
}
}
return new String(result);
}
https://leetcode.com/discuss/108232/java_solution_in_12_ms-o-n-time-and-space

https://leetcode.com/discuss/108174/c-unordered_map-priority_queue-solution-using-cache
http://www.cnblogs.com/grandyang/p/5586009.html

```    string rearrangeString(string str, int k) {
if (k == 0) return str;
string res;
int len = (int)str.size();
unordered_map<char, int> m;
priority_queue<pair<int, char>> q;
for (auto a : str) ++m[a];
for (auto it = m.begin(); it != m.end(); ++it) {
q.push({it->second, it->first});
}
while (!q.empty()) {
vector<pair<int, int>> v;
int cnt = min(k, len);
for (int i = 0; i < cnt; ++i) {
if (q.empty()) return "";
auto t = q.top(); q.pop();
res.push_back(t.second);
if (--t.first > 0) v.push_back(t);
--len;
}
for (auto a : v) q.push(a);
}
return res;
}```
https://discuss.leetcode.com/topic/48125/java_solution_in_12_ms-o-n-time-and-space
``````    public String rearrangeString(String str, int k) {
if(k < 2) return str;
int[] times = new int[26];
for(int i = 0; i < str.length(); i++){
++times[str.charAt(i) - 'a'];
}
SortedSet<int[]> set = new TreeSet<int[]>(new Comparator<int[]>(){
@Override
public int compare(int[] a, int[] b){
return a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]);
}
});
for(int i = 0; i < 26; i++){
if(times[i] != 0){
}
}
int cycles = 0;
int cur = cycles;
Iterator<int[]> iter = set.iterator();
char[] res = new char[str.length()];
while(iter.hasNext()){
int[] e = iter.next();
for(int i = 0; i < e[0]; i++){
res[cur] = (char)('a'+e[1]);
if(cur > 0 && res[cur] == res[cur-1])
return "";
cur += k;
if(cur >= str.length()){
cur = ++cycles;
}
}
}
return new String(res);
}``````
http://blog.csdn.net/jmspan/article/details/51678257

1.     public String rearrangeString(String str, int k) {
2.         if (k <= 0return str;
3.         int[] f = new int[26];
4.         char[] sa = str.toCharArray();
5.         for(char c: sa) f[c-'a'] ++;
6.         int r = sa.length / k;
7.         int m = sa.length % k;
8.         int c = 0;
9.         for(int g: f) {
10.             if (g-r>1return "";
11.             if (g-r==1) c ++;
12.         }
13.         if (c>m) return "";
14.         Integer[] pos = new Integer[26];
15.         for(int i=0; i<pos.length; i++) pos[i] = i;
16.         Arrays.sort(pos, new Comparator<Integer>() {
17.            @Override
18.            public int compare(Integer i1, Integer i2) {
19.                return f[pos[i2]] - f[pos[i1]];
20.            }
21.         });
22.         char[] result = new char[sa.length];
23.         for(int i=0, j=0, p=0; i<sa.length; i++) {
24.             result[j] = (char)(pos[p]+'a');
25.             if (-- f[pos[p]] == 0) p ++;
26.             j += k;
27.             if (j >= sa.length) {
28.                 j %= k;
29.                 j ++;
30.             }
31.         }
32.         return new String(result);
33.     }

X.
https://discuss.leetcode.com/topic/48260/java-15ms-solution-with-two-auxiliary-array-o-n-time/
This looks like O(N^2) time because findValidMax() is linear.
Since the array is fixed size(26), it will take constant time to find max
This is a greedy problem.
Every time we want to find the best candidate: which is the character with the largest remaining count. Thus we will be having two arrays.
One count array to store the remaining count of every character. Another array to keep track of the most left position that one character can appear.
We will iterated through these two array to find the best candidate for every position. Since the array is fixed size, it will take constant time to do this.
After we find the candidate, we update two arrays.
``````    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;
}``````
https://segmentfault.com/a/1190000005825133
``````//先记录str中的char及它出现在次数，存在count[]里，用valid[]来记录这个char最小出现的位置。
//每一次把count值最大的数选出来，append到新的string后面
public int selectedValue(int[] count, int[] valid, int i) {
int select = Integer.MIN_VALUE;
int val = -1;
for (int j = 0; j < count.length; j++) {
if (count[j] > 0 && i >= valid[j] && count[j] > select) {
select = count[j];
val = j;
}
}
return val;
}

public String rearrangeString(String str, int k) {
int[] count = new int[26];
int[] valid = new int[26];
//把每个出现了的char的个数记下来
for (char c : str.toCharArray()) {
count[c - 'a']++;
}

StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
//选出剩下需要出现次数最多又满足条件的字母，即是我们最应该先放的数
int curt = selectedValue(count, valid, i);
//如果不符合条件，返回“”
if (curt == -1) return "";
//选择好后，count要减少，valid要到下一个k distance之后
count[curt]--;
valid[curt] = i + k;
sb.append((char)('a' + curt));
}

return sb.toString();
}``````
https://reeestart.wordpress.com/201
1.     public String rearrangeString(String str, int k) {
2.         if (str == null || str.length() <= 1 || k <= 0return str;
3.         char[] sa = str.toCharArray();
4.         int[] frequency = new int[26];
5.         for(char ch : sa) {
6.             frequency[ch - 'a'] ++;
7.         }
8.         int bucketSize = sa.length / k;
9.         int remainSize = sa.length % k;
10.         int[] remain = new int[remainSize];
11.         int count = 0;
12.         for(int i = 0; i < frequency.length; i++) {
13.             if (frequency[i] > bucketSize + 1return "";
14.             if (frequency[i] > bucketSize && count >= remainSize) return "";
15.             if (frequency[i] > bucketSize) remain[count++] = i;
16.         }
17.
18.         int offset = 0, j = 0;
19.         for(int i = 0; i < count; i++) {
20.             while (frequency[remain[i]] > 0) {
21.                 frequency[remain[i]] --;
22.                 sa[j] = (char)('a' + remain[i]);
23.                 j += k;
24.                 if (j >= sa.length) {
25.                     offset ++;
26.                     j = offset;
27.                 }
28.             }
29.         }
30.
31.         for(int i = 0; i < 26; i ++) {
32.             while (frequency[i] > 0) {
33.                 frequency[i] --;
34.                 sa[j] = (char)('a' + i);
35.                 j += k;
36.                 if (j >= sa.length) {
37.                     offset ++;
38.                     j = offset;
39.                 }
40.             }
41.         }
42.         return new String(sa);
43.     }
6/06/23/rearrange-string-with-k-distance-apart/

`  ``public` `String rearrangeString(String str, ``int` `k) {`
`    ``if` `(str == ``null` `|| str.isEmpty() || k <= ``1``) {`
`      ``return` `str;`
`    ``}`
`    ``int``[] cnt = ``new` `int``[``26``];`
`    ``for` `(``char` `c : str.toCharArray()) {`
`      ``cnt[c - ``'a'``]++;`
`    ``}`
`//    List<int[]> entryList = new ArrayList<>();`
`//    for (int i = 0; i < 26; i++) {`
`//      if (cnt[i] != 0) {`
`//        entryList.add(new int[] {i, cnt[i]});`
`//      }`
`//    }`
`//    Collections.sort(entryList, (a, b) -> (-(a[1] - b[1])));`
`    ``TreeSet<``int``[]> entryList = ``new` `TreeSet<>(``new` `Comparator<``int``[]>() {`
`      ``public` `int` `compare(``int``[] a, ``int``[] b) {`
`        ``if` `(a[``1``] == b[``1``]) {`
`          ``return` `a[``0``] - b[``0``];`
`        ``}`
`        ``return` `-(a[``1``] - b[``1``]);`
`      ``}`
`    ``});`
`    ``for` `(``int` `i = ``0``; i < ``26``; i++) {`
`      ``if` `(cnt[i] != ``0``) {`
`        ``entryList.add(``new` `int``[] {i, cnt[i]});`
`      ``}`
`    ``}`
`    ``char``[] ch = ``new` `char``[str.length()];`
`    ``int` `i = ``0``;`
`    ``int` `start = ``1``;`
`    ``for` `(``int``[] entry : entryList) {`
`      ``for` `(``int` `j = ``0``; j < entry[``1``]; j++) {`
`        ``ch[i] = (``char``) (entry[``0``] + ``'a'``);`
`        ``if` `(i != ``0` `&& ch[i] == ch[i - ``1``]) {`
`          ``return` `""``;`
`        ``}`
`        ``i += k;`
`        ``if` `(i >= str.length()) {`
`          ``i = start;`
`          ``start++;`
`        ``}`
`      ``}`
`    ``}`
`    ``return` `new` `String(ch);`
`  ``}`
http://www.geeksforgeeks.org/check-whether-strings-k-distance-apart-not/
Given two strings, the task is to find if they are only less than or equal to k edit distance apart. It means that strings are only k edit distance apart when there are only k mismatches.
Print Yes if there are less than or equal to k mismatches, Else No.
Also print yes if both strings are already same.
1- Check if the difference in the length of both strings is greater than k if so , return false.
2- Find edit distance of two strings. If edit distance is less than or equal to k, return true. Else return false.
`int` `editDistDP(string str1, string str2, ``int` `m, ``int` `n)`
`{`
`    ``// Create a table to store results of subproblems`
`    ``int` `dp[m+1][n+1];`
`    ``// Fill d[][] in bottom up manner`
`    ``for` `(``int` `i=0; i<=m; i++)`
`    ``{`
`        ``for` `(``int` `j = 0; j<=n; j++)`
`        ``{`
`            ``// If first string is empty, only option is to`
`            ``// insert all characters of second string`
`            ``if` `(i == 0)`
`                ``dp[i][j] = j;  ``// Min. operations = j`
`            ``// If second string is empty, only option is to`
`            ``// remove all characters of second string`
`            ``else` `if` `(j == 0)`
`                ``dp[i][j] = i; ``// Min. operations = i`
`            ``// If last characters are same, ignore last char`
`            ``// and recur for remaining string`
`            ``else` `if` `(str1[i-1] == str2[j-1])`
`                ``dp[i][j] = dp[i-1][j-1];`
`            ``// If last character are different, consider all`
`            ``// possibilities and find minimum`
`            ``else`
`                ``dp[i][j] = 1 + min(dp[i][j-1],  ``// Insert`
`                                   ``dp[i-1][j],  ``// Remove`
`                                   ``dp[i-1][j-1]); ``// Replace`
`        ``}`
`    ``}`
`    ``return` `dp[m][n];`
`}`
`// Returns true if str1 and str2 are k edit distance apart,`
`// else false.`
`bool` `areKDistant(string str1, string str2, ``int` `k)`
`{`
`    ``int` `m = str1.length();`
`    ``int` `n = str2.length();`
`    ``if` `(``abs``(m-n) > k)`
`        ``return` `false``;`
`    ``return` `(editDistDP(str1, str2, m, n) <= k);`
`}`