String Reorder Distance Apart | LeetCode
Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }
http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away/
This is a different question.
-- In Java, use PriortiyQueue: element is Pair<Charcter, Integer>
https://github.com/Kelvinli1988/leetcode/blob/master/1/ReorderDistanceApart.java
https://learn.hackerearth.com/forum/476/given-a-string-of-lowercase-characters-reorder-them-such-that-the-same-characters-are-at-least-dis/
http://www.cnblogs.com/ZJUKasuosuo/archive/2012/08/12/2634765.html
http://7371901.blog.51cto.com/7361901/1605271
http://yuanhsh.iteye.com/blog/2231105
http://7371901.blog.51cto.com/7361901/1605271
https://gist.github.com/gcrfelix/cd4f4e887e41882ca1f2
public class Solution {
public char[] getMinDistance(char[] chars, int minDistance) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<chars.length; i++) {
char c = chars[i];
if(map.containsKey(c)) {
map.put(c, map.get(c)+1);
} else {
map.put(c, 1);
}
}
PriorityQueue<Element> maxHeap = new PriorityQueue<Element>(1, new Comparator<Element>() {
public int compare(Element e1, Element e2) {
return e2.count - e1.count;
}
});
for(char c : map.keySet()) {
int count = map.get(c);
Element e = new Element(c, count);
maxHeap.offer(e);
}
int index = 0;
char[] result = new char[chars.length];
while(!maxHeap.isEmpty()) {
Queue<Element> queue = new LinkedList<Element>();
int i=0;
for(; i<minDistance && !maxHeap.isEmpty(); i++) {
queue.offer(maxHeap.poll());
}
if(i < minDistance && queue.peek().count > 1) { // 说明不可能有这样的char组合满足minDistance
return new char[0];
}
while(!queue.isEmpty()) {
Element e = queue.poll();
result[index++] = e.c;
e.count --;
if(e.count > 0) {
maxHeap.offer(e);
}
}
}
return result;
}
}
class Element {
char c;
int count;
public Element(char c, int count) {
this.c = c;
this.count = count;
}
}
https://discuss.leetcode.com/topic/102/rearrange-string
Given a string S, and an integer K, rearrange the string such that similar characters are at least K distance apart.
Example:
S = AAABBBCC, K = 3
Result : ABCABCABC (all 'A's are 3 distance apart, similarly with B's and C's)
S = AAABC, K=2 : Not possible. (EDIT : k=3 is not possible).
S = AAADBBCC, K = 2:
Result: ABCABCDA
the algorithm above works only if the same characters are at exact d characters apart. Here is a modification on it to take into account the "at least d" condition. The idea is the same with exception that when the last free slot is after the last position of the letter with maximum frequence, we start to insert characters from the beginning of the string at "d" distance.
-- not good code
Given a task sequence tasks such as ABBABBC, and an integer k, which is the cool down time between two same tasks. Assume the execution for each individual task is 1 unit.
For example, if k = 3, then tasks BB takes a total of 5 unit time to finish, because B takes 1 unit of time to execute, then wait for 3 unit, and execute the second B again for another unit of time. So 1 + 3 + 1 = 5.
Given a task sequence and the cool down time, return the total execution time.
Follow up: Given a task sequence and the cool down time, rearrange the task sequence such that the execution time is minimal.
I think that the follow up of the problem is very common to the problem https://discuss.leetcode.com/topic/102/rearrange-string.We will try greedy to arrange tasks with distance 2.in case this doesn't work, we will not return "no possible arrangement",but we will put the same tasks one to another
https://github.com/mission-peace/interview/blob/master/src/com/interview/string/RearrangeDuplicateCharsdDistanceAway.java
Read full article from String Reorder Distance Apart | LeetCode
Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }
http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away/
This is a different question.
Solution: The idea is to count frequencies of all characters and consider the most frequent character first and place all occurrences of it as close as possible. After the most frequent character is placed, repeat the same process for remaining characters.
2) Traverse str, store all characters and their frequencies in a Max Heap MH. The value of frequency decides the order in MH, i.e., the most frequent character is at the root of MH.
4) Do following while MH is not empty.
…a) Extract the Most frequent character. Let the extracted character be x and its frequency be f.
…b) Find the first available position in str, i.e., find the first ‘\0′ in str.
…c) Let the first position be p. Fill x at p, p+d,.. p+(f-1)d
…b) Find the first available position in str, i.e., find the first ‘\0′ in str.
…c) Let the first position be p. Fill x at p, p+d,.. p+(f-1)d
Time Complexity: Time complexity of above implementation is O(n + mLog(MAX)).
struct
charFreq {
char
c;
int
f;
};
void
rearrange(
char
str[],
int
d)
{
// Find length of input string
int
n =
strlen
(str);
// Create an array to store all characters and their
// frequencies in str[]
charFreq freq[MAX] = {{0, 0}};
int
m = 0;
// To store count of distinct characters in str[]
// Traverse the input string and store frequencies of all
// characters in freq[] array.
for
(
int
i = 0; i < n; i++)
{
char
x = str[i];
// If this character has occurred first time, increment m
if
(freq[x].c == 0)
freq[x].c = x, m++;
(freq[x].f)++;
str[i] =
'\0'
;
// This change is used later
}
// Build a max heap of all characters
buildHeap(freq, MAX);
// Now one by one extract all distinct characters from max heap
// and put them back in str[] with the d distance constraint
for
(
int
i = 0; i < m; i++)
{
charFreq x = extractMax(freq, MAX-i);
// Find the first available position in str[]
int
p = i;
while
(str[p] !=
'\0'
)
p++;
// Fill x.c at p, p+d, p+2d, .. p+(f-1)d
for
(
int
k = 0; k < x.f; k++)
{
// If the index goes beyond size, then string cannot
// be rearranged.
if
(p + d*k >= n)
{
cout <<
"Cannot be rearranged"
;
exit
(0);
}
str[p + d*k] = x.c;
}
}
}
The solution below involves a greedy strategy, that is: The character that has the most duplicates has the highest priority of being chosen to put in the new list. If that character cannot be chosen (due to the distance constraint), we go for the character that has the next highest priority. We also use some tables to improve the efficiency. (i.e., keeping track of # of duplicates of each character.)
int
find_max(
int
freq[],
bool
except[])
{
int
max_i = -1;
int
max = -1;
for
(
char
c =
'a'
; c <=
'z'
; c++)
{
if
(!except[c] && freq[c] > 0 && freq[c] > max)
{
max = freq[c];
max_i = c;
}
}
return
max_i;
}
void
create(
char
*str,
int
distance,
char
ans[])
{
int
n =
strlen
(str);
int
freq[256] = { 0 };
for
(
int
i = 0; i < n; i++)
freq[str[i]]++;
int
used[256] = { 0 };
for
(
int
i = 0; i < n; i++){
bool
execp[256] = {
false
};
bool
done =
false
;
while
(!done){
int
j = find_max(freq, execp);
if
(j == -1)
{
cout <<
"Error!\n"
;
return
;
}
execp[j] =
true
;
if
(used[j] <= 0){
ans[i] = j;
freq[j]--;
used[j] = distance;
done =
true
;
}
}
for
(
int
i = 0; i < 256; i++)
used[i]--;
}
ans[n] =
'\0'
;
}
https://learn.hackerearth.com/forum/476/given-a-string-of-lowercase-characters-reorder-them-such-that-the-same-characters-are-at-least-dis/
http://www.cnblogs.com/ZJUKasuosuo/archive/2012/08/12/2634765.html
http://7371901.blog.51cto.com/7361901/1605271
Solution: The idea is to count frequencies of all characters and consider the most frequent character first and place all occurrences of it as close as possible. After the most frequent character is placed, repeat the same process for remaining characters.
1) Let the given string be str and size of string be n
2) Traverse str, store all characters and their frequencies in a Max Heap MH. The value of frequency decides the order in MH, i.e., the most frequent character is at the root of MH.
3) Make all characters of str as ‘\0′.
4) Do following while MH is not empty.
…a) Extract the Most frequent character. Let the extracted character be x and its frequency be f.
…b) Find the first available position in str, i.e., find the first ‘\0′ in str.
…c) Let the first position be p. Fill x at p, p+d,.. p+(f-1)d
…a) Extract the Most frequent character. Let the extracted character be x and its frequency be f.
…b) Find the first available position in str, i.e., find the first ‘\0′ in str.
…c) Let the first position be p. Fill x at p, p+d,.. p+(f-1)d
Time Complexity: O(n+mlog(m)). Here n is the length of str, m is count of distinct characters in str[]. m is smaller than 256. So the time complexity can be considered as O(n).
- public static String rearrange(String str, int k) {
- Map<Character, Integer> map = new HashMap<>();
- char[] s = str.toCharArray();
- int n = s.length;
- for(int i=0; i<n; i++) {
- Integer cnt = map.get(s[i]);
- if(cnt == null) cnt = 0;
- map.put(s[i], cnt+1);
- }
- Queue<Character> queue = new PriorityQueue<>(map.size(), new Comparator<Character>(){
- public int compare(Character c1, Character c2) {
- return map.get(c2) - map.get(c1);
- }
- });
- queue.addAll(map.keySet());
- Arrays.fill(s, '\0');
- for(int i=0; i<map.size(); i++) {
- int p = i;
- while(s[p] != '\0') p++;
- char c = queue.poll();
- int cnt = map.get(c);
- for(int j=0; j<cnt; j++) {
- if(p >= n) return "Cannot be rearranged";
- s[p] = c;
- p += k;
- }
- }
- return new String(s);
- }
public
void
reorder(
int
[] A,
int
d)
{
// Stats
Map<Integer, Integer> map =
new
HashMap<>();
for
(
int
i : A)
{
Integer occurance = map.get(i);
if
(occurance ==
null
)
occurance =
0
;
occurance++;
map.put(i, occurance);
}
// Sort
List<Map.Entry<Integer, Integer>> list =
new
ArrayList<>(map.entrySet());
Collections.sort(list,
new
Comparator<Map.Entry<Integer, Integer>>()
{
public
int
compare(Entry<Integer, Integer> a, Entry<Integer, Integer> b)
{
return
-
1
* Integer.compare(a.getValue(), b.getValue());
}
});
// Re-assign
int
curIndex =
0
;
Map.Entry<Integer, Integer> cur = list.get(curIndex);
int
curOccurance =
0
;
for
(
int
offset =
0
; offset < d; offset++)
{
for
(
int
i = offset; i < A.length; i += d)
{
A[i] = cur.getKey();
curOccurance++;
if
(curOccurance == cur.getValue())
{
curIndex++;
if
(curIndex == list.size())
return
;
cur = list.get(curIndex);
curOccurance =
0
;
}
}
}
}
public class Solution {
public char[] getMinDistance(char[] chars, int minDistance) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<chars.length; i++) {
char c = chars[i];
if(map.containsKey(c)) {
map.put(c, map.get(c)+1);
} else {
map.put(c, 1);
}
}
PriorityQueue<Element> maxHeap = new PriorityQueue<Element>(1, new Comparator<Element>() {
public int compare(Element e1, Element e2) {
return e2.count - e1.count;
}
});
for(char c : map.keySet()) {
int count = map.get(c);
Element e = new Element(c, count);
maxHeap.offer(e);
}
int index = 0;
char[] result = new char[chars.length];
while(!maxHeap.isEmpty()) {
Queue<Element> queue = new LinkedList<Element>();
int i=0;
for(; i<minDistance && !maxHeap.isEmpty(); i++) {
queue.offer(maxHeap.poll());
}
if(i < minDistance && queue.peek().count > 1) { // 说明不可能有这样的char组合满足minDistance
return new char[0];
}
while(!queue.isEmpty()) {
Element e = queue.poll();
result[index++] = e.c;
e.count --;
if(e.count > 0) {
maxHeap.offer(e);
}
}
}
return result;
}
}
class Element {
char c;
int count;
public Element(char c, int count) {
this.c = c;
this.count = count;
}
}
https://discuss.leetcode.com/topic/102/rearrange-string
Given a string S, and an integer K, rearrange the string such that similar characters are at least K distance apart.
Example:
S = AAABBBCC, K = 3
Result : ABCABCABC (all 'A's are 3 distance apart, similarly with B's and C's)
S = AAABC, K=2 : Not possible. (EDIT : k=3 is not possible).
S = AAADBBCC, K = 2:
Result: ABCABCDA
the algorithm above works only if the same characters are at exact d characters apart. Here is a modification on it to take into account the "at least d" condition. The idea is the same with exception that when the last free slot is after the last position of the letter with maximum frequence, we start to insert characters from the beginning of the string at "d" distance.
-- not good code
public String rearrange(String s, int d) {
Map<Character, Integer> map = new HashMap<>();
int n = s.length();
for (int i=0; i < n; i++) {
Integer cnt = map.get(s.charAt(i));
if (cnt == null)
cnt = 0;
map.put(s.charAt(i), cnt+1);
}
Queue<Character> queue = new PriorityQueue<>(map.size(), new Comparator<Character>(){
public int compare(Character c1, Character c2) {
return map.get(c2) - map.get(c1);
}
});
queue.addAll(map.keySet());
StringBuilder sb = new StringBuilder(n);
int sz = n;
while (sz > 0) {
sb.append('\0');
sz--;
}
int firstFree = 0;
int m = map.get(queue.peek());
while (!queue.isEmpty()) {
Character ch = queue.poll();
while (firstFree < n && sb.charAt(firstFree) != '\0')
firstFree++;
int q = 0;
if (firstFree == n)
return "Cannot be rearranged";
if (firstFree < d*m - 1) {
q = firstFree;
firstFree++;
}
int cnt = map.get(ch);
while (q < n && cnt > 0 ) {
if (sb.charAt(q) == '\0')
sb.setCharAt(q, ch);
else
sb.insert(q, ch);
q+=d;
cnt--;
}
if(cnt > 0)
return "Cannot be rearranged";
}
return new String(sb.toString().substring(0, n));
}
https://discuss.leetcode.com/topic/112/minimal-run-time-schedulerGiven a task sequence tasks such as ABBABBC, and an integer k, which is the cool down time between two same tasks. Assume the execution for each individual task is 1 unit.
For example, if k = 3, then tasks BB takes a total of 5 unit time to finish, because B takes 1 unit of time to execute, then wait for 3 unit, and execute the second B again for another unit of time. So 1 + 3 + 1 = 5.
Given a task sequence and the cool down time, return the total execution time.
Follow up: Given a task sequence and the cool down time, rearrange the task sequence such that the execution time is minimal.
I think that the follow up of the problem is very common to the problem https://discuss.leetcode.com/topic/102/rearrange-string.We will try greedy to arrange tasks with distance 2.in case this doesn't work, we will not return "no possible arrangement",but we will put the same tasks one to another
https://github.com/mission-peace/interview/blob/master/src/com/interview/string/RearrangeDuplicateCharsdDistanceAway.java
Read full article from String Reorder Distance Apart | LeetCode