Massive Algorithms: Rearrange Characters in String With No Adjacent Duplicate Characters

Given a string, rearrange characters of the string such that no duplicate characters are adjacent to each other.

In order to implement the above idea we can maintain a MaxHeap of character frequency histogram. Each time we try to extract two top most frequent characters and place them in adjacent positions. Then we add those characters back to the heap with decreased frequency (why?). This way we guarantee that the arrangement doesn’t have any two repeating element in adjacent places. The following implementation is based on using PriorityQueue for max heap. Time complexity is O(n) to build the initial heap and O(nlgn) to update the heap for each pair of character realignment.

public static String rearrangeAdjacentDuplicates(String str){
 final class CharFreq implements Comparable<CharFreq>{
  char c;
  int freq;
  public CharFreq(char ch, int count){
   c = ch;
   freq = count;
  }
  @Override
  public int compareTo(CharFreq o) {
   int comp = Double.compare(freq, o.freq);
   if(comp == 0){
    comp = Character.compare(o.c, c);
   }
   
   return comp;
  }
 }
 
 int n = str.length();
 StringBuffer rearranged = new StringBuffer();
 PriorityQueue<CharFreq> maxHeap = new PriorityQueue<CharFreq>(256, Collections.reverseOrder());
 int freqHistoGram[] = new int[256];
 //build the character frequency histogram
 for(char c : str.toCharArray()){
  freqHistoGram[c]++;
  
  //if a character repeats more than n/2 then we can't rearrange
  if(freqHistoGram[c] > (n+1)/2){
   return str; // throe ex;
  }
 }
 //build the max heap of histogram
 for(char i  = 0; i < 256; i++){
  if(freqHistoGram[i] > 0)
   maxHeap.add(new CharFreq(i, freqHistoGram[i]));
 }
 
 //rearrange - pop top 2 most frequent items and arrange them in adjacent positions
 //decrease the histogram frequency of the selected chars 
 while(!maxHeap.isEmpty()){
  //extract top one and decrease the hstogram by one
  CharFreq first = maxHeap.poll();
  rearranged.append(first.c);
  first.freq--;
  
  CharFreq second = null;
  //extract second top and decrease the histogram by one
  if(!maxHeap.isEmpty()){
   second = maxHeap.poll();
   rearranged.append(second.c);
   second.freq--;
  }
  
  //add back the updated histograms 
  if(first.freq > 0){
   maxHeap.add(first);
  }
  if(second != null && second.freq > 0){
   maxHeap.add(second);
  }
 }
 
 return rearranged.toString();
}

https://gist.github.com/gcrfelix/672a4c7952c02e57aee5
题目大致是BACCBBAAA -> ABABACABC，就是输出相邻字母不能相同的string

解题思路：建立一个maxHeap，按char在string里出现的次数存char，然后不断pop后再加入heap中重新排序，就是每次把出现次数最多的字母先解决

public class Solution {
public String rearrangeString(String s) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<s.length(); i++) {
char c = s.charAt(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);
}

StringBuilder sb = new StringBuilder();
while(!maxHeap.isEmpty()) {
Element e1 = maxHeap.poll();
if(maxHeap.isEmpty()) { // maxHeap里还有最后一个char时的处理办法
sb.append(e1.c);
break;
}
Element e2 = maxHeap.poll();
sb.append(e1.c);
sb.append(e2.c); // this work???
if(e1.count > 1) {
e1.count --;
maxHeap.offer(e1);
}
if(e2.count > 1) {
e2.count --;
maxHeap.offer(e2);
}
}
return sb.toString();
}
}

http://www.geeksforgeeks.org/rearrange-characters-string-no-two-adjacent/

Given a string with repeated characters, task is rearrange characters in a string so that no two adjacent characters are same.

The idea is to put highest frequency character first (a greedy approach). We use a priority queue (Or Binary Max Heap) and put all characters and ordered by their frequencies (highest frequency character at root). We one by one take highest frequency character from the heap and add it to result. After we add, we decrease frequency of the character and we temporarily move this character out of priority queue so that it is not picked next time.

Time complexity : O(n log n)

void rearrangeString(string str)

{

    int n = str.length();

    // Store frequencies of all characters in string

    int count[MAX_CHAR] = {0};

    for (int i = 0 ; i < n ; i++)

        count[str[i]-'a']++;

    // Insert all characters with their frequencies

    // into a priority_queue

    priority_queue< Key > pq;

    for (char c = 'a' ; c <= 'z' ; c++)

        if (count[c-'a'])

            pq.push( Key { count[c-'a'], c} );

    // 'str' that will store resultant value

    str = "" ;

    // work as the previous visited element

    // initial previous element be. ( '#' and

    // it's frequency '-1' )

    Key prev {-1, '#'} ;

    // traverse queue

    while (!pq.empty())

{

        // pop top element from queue and add it

        // to string.

        Key k = pq.top();

        pq.pop();

        str = str + k.ch;

        // IF frequency of previous character is less

        // than zero that means it is useless, we

        // need not to push it

        if (prev.freq > 0)

            pq.push(prev);

        // make current character as the previous 'char'

        // decrease frequency by 'one'

        (k.freq)--;

        prev = k;

}

    // If length of the resultant string and original

    // string is not same then string is not valid

    if (n != str.length())

        cout << " Not valid String " << endl;

    else // valid string

        cout << str << endl;

}

Read full article from Rearrange Characters in String With No Adjacent Duplicate Characters - Algorithms and Problem SolvingAlgorithms and Problem Solving

Rearrange Characters in String With No Adjacent Duplicate Characters

Labels

Popular Posts