Reorganize String II

Innoskrit August 19, 2022 Innoskrit Masterclass DSA Sheet, Priority Queue (Heap)

Problem Statement

Given a string and a number ‘K’, find if the string can be rearranged such that the same characters are at least ‘K’ distance apart from each other.

Example:

Input 1: s = "mmpp", K = 2
Output 1: "pmpm"

Input 2: s = "aaaaabbbcccddd", K = 3
Output 2: "adcabdacbadcba"

Code

Java

C++

Python

import java.util.*;

class Innoskrit {

    public static String reorganizeString(String str, int k) {
    
        if (k <= 1) {
            return str;
        }
        
        Map<Character, Integer> freqMap = new HashMap<>();
        
        for (char chr : str.toCharArray()) {
            freqMap.put(chr, freqMap.getOrDefault(chr, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<Map.Entry<Character, Integer>>(
            (e1, e2) -> e2.getValue() - e1.getValue());
        
        maxHeap.addAll(freqMap.entrySet());
        
        Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
        StringBuilder resultString = new StringBuilder(str.length());
        
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> currentEntry = maxHeap.poll();
            
            resultString.append(currentEntry.getKey());
            currentEntry.setValue(currentEntry.getValue() - 1);
            queue.offer(currentEntry);
            
            if (queue.size() == k) {
                Map.Entry<Character, Integer> entry = queue.poll();
                if (entry.getValue() > 0) {
                    maxHeap.add(entry);
                }
            }
        }
        
        return resultString.length() == str.length() ? resultString.toString() : "";
    }
    
    public static void main(String[] args) {
        System.out.println(Innoskrit.reorganizeString("mmpp", 2));
        System.out.println(Innoskrit.reorganizeString("aaaaabbbcccddd", 3));
    }
}

#include <bits/stdc++.h>
using namespace std;

class Innoskrit {
    public:
        struct comparator {
            bool operator()(const pair<int, int> &x, const pair<int, int> &y) {
                return y.second > x.second;
            }
        };

        static string reorganizeString(const string &str, int k) {
            if (k <= 1) {
                return str;
            }
            
            unordered_map<char, int> freqMap;
            for (char chr : str) {
                freqMap[chr]++;
            }
            
            priority_queue<pair<char, int>, vector<pair<char, int>>, comparator> maxHeap;
            
            for (auto entry : freqMap) {
                maxHeap.push(entry);
            }
            
            queue<pair<char, int>> queue;
            string resultString;
            while (!maxHeap.empty()) {
                auto currentEntry = maxHeap.top();
                maxHeap.pop();
                resultString += currentEntry.first;
                currentEntry.second--;
                queue.push(currentEntry);
                if (queue.size() == k) {
                    auto entry = queue.front();
                    queue.pop();
                    if (entry.second > 0) {
                        maxHeap.push(entry);
                    }
                }
            }
            
            return resultString.length() == str.length() ? resultString : "";
        }
};

int main(int argc, char *argv[]) {
    cout << Innoskrit::reorganizeString("mmpp", 2) << endl;
    cout << Innoskrit::reorganizeString("aaaaabbbcccddd", 3) << endl;
}

from heapq import *
from collections import deque

class Pair:
    
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
    
    def __lt__(self, other):
        return self.freq > other.freq
    
class Innoskrit:
    
    @staticmethod
    def reorganize_string(str, k):
        if k <= 1: 
            return str
    
        freq_map = {}
        for char in str:
            freq_map[char] = freq_map.get(char, 0) + 1
    
        maxHeap = []
    
        for char, frequency in freq_map.items():
            heappush(maxHeap, Pair(char, frequency))
    
        queue = deque()
        resultString = []
        while maxHeap:
            entry = heappop(maxHeap)
    
            resultString.append(entry.char)
            entry.freq -= 1
            queue.append(entry)
            if len(queue) == k:
                entry = queue.popleft()
                if entry.freq > 0:
                    heappush(maxHeap, entry)
                
        return ''.join(resultString) if len(resultString) == len(str) else ""
    
if __name__ == '__main__':
    
    print(Innoskrit.reorganize_string("mmpp", 2))
    print(Innoskrit.reorganize_string("aaaaabbbcccddd", 3))

Output:

pmpm
adcabdacbadcba

Time and Space Complexity

Time Complexity: The time complexity of the above algorithm is O(N∗logN) where ‘N’ is the number of characters in the input string.

Space Complexity: The space complexity will be O(N), as in the worst case, we need to store all the ‘N’ characters in the HashMap.