Rearrange string k distance apart

Introduction

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.

Solution

First of all, create a Pair class that has three properties: character c, count of the character and a timestamp (timestamp is used in priority queue to maintain descending order). Then create a priority queue based on the count of the character and timestamp when counts are equal to ensure FIFO order. Create a pair for each unique character with its count after traversing the whole string and add all pairs to priority queue, then pop out k pairs with each minus one if the queue is not empty. If the count is not zero, add it to a temporary list and put it back to queue at the end. At the same time add current character to string builder. For cases that do not have an answer, this line of code if(pair.count >= 1 && queue.size() + temp.size() < k) return ""; will check if current character will appear sometime later but there are not enough characters to set them k distance apart.

public class RearrangeStringKDistanceApart {

  class Pair {
    public char c;
    public int count;
    public int timestamp = 0;

    public Pair(char c, int count, int timestamp) {
      this.c = c;
      this.count = count;
      this.timestamp = timestamp;
    }
  }

  public String rearrangeString(String s, int k) {
    if(k == 0) return s;
        int[] map = new int[26];
        int time = 0;
        StringBuilder builder = new StringBuilder();
        PriorityQueue<Pair> queue = new PriorityQueue<>(
              (a, b) -> (a.count == b.count)? a.timestamp - b.timestamp : b.count - a.count);

        for(int i=0; i<s.length(); i++) map[s.charAt(i) - 'a']++;

        for(int i=0; i<map.length; i++) {
          if(map[i] > 0) {
            Pair pair = new Pair((char)('a' + i), map[i], time++);
            queue.add(pair);
          }
        }

        while(!queue.isEmpty()) {
          List<Pair> temp = new ArrayList<>();
          for(int i=0; i<k; i++) {
            if(!queue.isEmpty()) {
              Pair pair = queue.poll();
              pair.count--;
              if(pair.count >= 1) {
                pair.timestamp = time++;
                temp.add(pair);
              }
              builder.append(pair.c);
              if(pair.count >= 1 && queue.size() + temp.size() < k) return "";
            }
          }

          for(Pair p : temp) queue.add(p);
        }

        return builder.toString();
    }

  public static void main(String[] args) {
    RearrangeStringKDistanceApart r = new RearrangeStringKDistanceApart();
    // String s = "aaadbbcc";
    String s = "abb";
    int k = 12;
    // String s = "aabbcc";
    // int k = 3;
    System.out.println(r.rearrangeString(s, k));
  }
}