Home » Technical Interview Questions » String Interview Questions » Reorganize String

Reorganize String


Reading Time - 4 mins

In Reorganize String problem we have given a string containing some characters “a-z” only. Our task is to rearrange those characters such that no two same characters are adjacent to each other.

Example

Input

apple

Output

pelpa

Input

book

Output

obko

Input

aa

Output

not possible

Input

aaab

Output

not possible

Explanation for Reorganize String

To solve this problem we shall implement a priority queue by using max heap in which we have to put the highest frequency character first(greed approach). After that, we will put all the characters in our priority queue/max heap and ordered by their frequency(highest frequency character at the root). The character with the highest frequency will be taken from the heap and will be added to the resultant string. The frequency of that character will be reduced and that character will be popped out of the priority queue.

Algorithm for Reorganize String

  1. Initialize a priority queue using max heap, “pq” which will store character with their frequencies.
  2. Create a temporary key which will work as the previously visited element in the resultant string. Initialize it {char = ‘$’, freq = -1}
  3. While “pq” is not empty.
    1. An element will be popped and added to the result.
    2. Decrease frequency of popped element by 1.
    3. Push the previous element back into the priority queue if it’s frequency > “0”.
    4. Make the current element as the previous element for the next iteration.
  4. Print “Not Possible” if the length of the original string and the resulting string is not equal. Else print result.
READ  Rabin Karp Algorithm

First, we make a class name key in which we could store the frequency of characters. After that, we override our compare method of Comparator interface such that, we could order all character by their frequencies. Then we make a function to rearrange our string in which we make priority queue “pq” to store characters in it and use keycomparator()  class to order character according to their frequencies and then traversing our queue through while loop so we could rearrange characters and finally compare the size of the original string and resultant string to get our rearranged string.

Implementation in C++

#include<iostream>
#include<queue>

using namespace std;

const int MAX_CHAR = 26;
struct Key
{
    int freq; // store frequency of character
    char ch;
    // function for priority_queue to store Key
    // according to freq
    bool operator<(const Key &k) const
    {
        return freq < k.freq;
    }
};

// Function to rearrange character of a string
// so that no char repeats twice
string Rearrange_String(string str)
{
    int original_size = str.length();
    // Store frequencies of all characters in string
    int count[MAX_CHAR] = {0};
    for (int i = 0 ; i < original_size; 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} );
        }
    }
    // 's' that will store resultant value
    string s = "" ;

    // work as the previous visited element
    // initial value for previous element be. ( '$' and
    // it's freq '-1' )
    Key prev {-1, '$'} ;
    // traversing queue
    while (!pq.empty())
    {
        // pop the top element from queue
        // add it to string 's'.

        Key k = pq.top();
        pq.pop();
        s = s + k.ch;

        // If frequency of previous character < 0
        // we need not to push it
        if (prev.freq > 0)
            pq.push(prev);

        // make current character as the previous character
        // decrease frequency by 1
        (k.freq)--;
        prev = k;
    }
    // If length of the final string and original
    // string is not same then it is not possible to rearrange.
    if (original_size != s.length())
        return "Not Possible";
    else
        // valid string
        return s;
}
// main function to test above function
int main()
{
    string str = "apple" ;
    cout<<Rearrange_String(str);
    return 0;
}
plaep

Implementation in Java

/* Java program to Reorganize string in such manner,
there should no same two adjacent string
*/
import java.io.*;
import java.util.*;

class Key {
  int freq; // store frequency of character
  char ch;
  Key(int val, char c) {
    freq = val;
    ch = c;
  }
}

class KeyComparator implements Comparator<Key> {

  // Overriding compare()method of Comparator
  public int compare(Key k1, Key k2) {
    if (k1.freq<k2.freq)
      return 1;
    else if (k1.freq > k2.freq)
      return -1;
    return 0;
  }
}

class reorganize_string {
  static int MAX_CHAR = 26;

  // Function to rearrange character of a string
  // so that no char repeats twice
  static String Rearrange_String(String str) {
    int original_size = str.length();

    // Store frequencies of all characters in string
    int[] count = new int[MAX_CHAR];

    for (int i = 0; i<original_size; i++)
      count[str.charAt(i) - 'a']++;

    // Insert all characters with their frequencies
    // into a priority_queue
    PriorityQueue<Key> pq = new PriorityQueue<>(new KeyComparator());
    for (char c = 'a'; c<= 'z'; c++) {
      int val = c - 'a';
      if (count[val] > 0)
        pq.add(new Key(count[val], c));
    }

    // 's' that will store resultant value
    String s = "";

    // work as the previous visited element
    // initial value for previous element be. ( '$' and
    // it's freq '-1' )
    Key prev = new Key(-1, '$');

    // traversing queue
    while (pq.size() != 0) {

      // pop the top element from queue
      // add it to string 's'.
      Key k = pq.peek();
      pq.poll();
      s = s + k.ch;

      // If frequency of previous character<0
      // we need not to push it
      if (prev.freq > 0)
        pq.add(prev);

      // make current character as the previous character
      // decrease frequency by 1
      (k.freq) --;
      prev = k;
    }

    // If length of the final string and original
    // string is not same then it is not possible to rearrange.
    if (original_size != s.length())
      return "Not Possible";
    else
      return s;
  }

  // main func to test above function
  public static void main(String args[]) {
    String str = "apple";
    System.out.println(Rearrange_String(str));
  }
}
pelpa

Complexity Analysis for Reorganize String

Time Complexity

O(n log A) where n is the length of string and A is the size of alphabets

READ  String comparison containing wildcards

Space Complexity

O(A) where A is the size of the alphabets.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions