Reorganize String

Solution For Reorganize String

Problem Statement:

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return “” if not possible.

Example 1:

Input: s = “aab”
Output: “aba”

Example 2:

Input: s = “aaab”
Output: “”

Approach:

The problem requires us to rearrange the input string such that no two adjacent characters are the same. We can approach the problem in the following way:

  1. First, we need to count the frequency of each character in the input string s. We can do this by creating a hash table that will store the count of each character.

  2. Next, we need to sort the characters in decreasing order of frequency. We can do this by creating a priority queue that will sort the characters based on their count.

  3. We can now start constructing the result string by appending the most frequent character to the result string first. Then we can append the next most frequent character to the result string, but only if it is not the same as the last character in the result string. We repeat this process until the result string is fully constructed.

  4. If at any point we encounter a character that cannot be added to the result string without violating the condition of not having two adjacent characters that are the same, we return “”.

Solution:

class Solution {
public:
string reorganizeString(string s) {

    // Count the frequency of each character in the string
    unordered_map<char, int> countMap;
    for (char c : s) {
        countMap[c]++;
    }

    // Create a priority queue to sort the characters in decreasing order of frequency
    priority_queue<pair<int, char>> pq;
    for (auto it : countMap) {
        pq.push({it.second, it.first});
    }

    // Construct the result string
    string result = "";
    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();
        if (result.empty() || curr.second != result.back()) {
            result += curr.second;
            if (--curr.first > 0) {
                pq.push(curr);
            }
        } else {
            return "";
        }
    }

    return result;
}

};

Complexity Analysis:

Time Complexity: O(nlogn), where n is the length of the input string s. We need to count the frequency of each character in the input string s which takes O(n) time. Sorting the characters in decreasing order of frequency using a priority queue takes O(nlogn) time in the worst case. Constructing the final string also takes O(n) time.

Space Complexity: O(n), where n is the length of the input string s. We need to store the count of each character in the input string s in a hash table which takes O(n) space. We also need to use a priority queue to sort the characters, which can take up to O(n) space in the worst case.

Step by Step Implementation For Reorganize String

class Solution {
    public String reorganizeString(String S) {
        // TODO: Implement solution
    }
}
class Solution:
    def reorganizeString(self, S: str) -> str:
        # create a list of tuples (letter, count)
        counts = collections.Counter(S).most_common()
        # if the most common letter occurs more than half the time, it can't be rearranged
        if counts[0][1] > (len(S) + 1) / 2:
            return ""
        
        # create a list of alternating letters starting with the most common one
        ans = [c for c, _ in counts]
        # fill in the remaining letters
        i = 0
        for c, _ in counts[1:]:
            ans[i] += c
            i += 2
            if i >= len(ans):
                i = 1
        return "".join(ans)
var reorganizeString = function(S) {
    // create a map to store the frequencies of each character
    let map = {};
    for (let char of S) {
        if (char in map) {
            map[char]++;
        } else {
            map[char] = 1;
        }
    }
    
    // create a min heap to store the characters in order of frequency
    let heap = new MinHeap();
    for (let char in map) {
        heap.insert(char, map[char]);
    }
    
    // build up the new string, alternate between the most and second most frequent characters
    let result = "";
    let mostFreq = heap.extractMin();
    let secondFreq = heap.extractMin();
    while (mostFreq && secondFreq) {
        for (let i = 0; i < Math.min(mostFreq[1], secondFreq[1]); i++) {
            result += mostFreq[0];
            result += secondFreq[0];
        }
        if (mostFreq[1] > secondFreq[1]) {
            result += mostFreq[0];
        }
        mostFreq = heap.extractMin();
        secondFreq = heap.extractMin();
    }
    // if there is only one character left in the heap, append it to the end of the string
    if (mostFreq) {
        result += mostFreq[0];
    }
    
    return result.length === S.length ? result : "";
};

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    insert(char, freq) {
        this.heap.push([char, freq]);
        this.heapifyUp(this.heap.length - 1);
    }
    
    heapifyUp(i) {
        let parentIdx = this.getParentIdx(i);
        if (parentIdx === -1) return;
        if (this.heap[parentIdx][1] > this.heap[i][1]) {
            this.swap(parentIdx, i);
            this.heapifyUp(parentIdx);
        }
    }
    
    extractMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        this.swap(0, this.heap.length - 1);
        let min = this.heap.pop();
        this.heapifyDown(0);
        return min;
    }
    
    heapifyDown(i) {
        let leftIdx = this.getLeftChildIdx(i);
        let rightIdx = this.getRightChildIdx(i);
        let smallestIdx = i;
        if (leftIdx !== -1 && this.heap[leftIdx][1] < this.heap[smallestIdx][1]) {
            smallestIdx = leftIdx;
        }
        if (rightIdx !== -1 && this.heap[rightIdx][1] < this.heap[smallestIdx][1]) {
            smallestIdx = rightIdx;
        }
        if (smallestIdx !== i) {
            this.swap(i, smallestIdx);
            this.heapifyDown(smallestIdx);
        }
    }
    
    getParentIdx(i) {
        return i === 0 ? -1 : Math.floor((i - 1) / 2);
    }
    
    getLeftChildIdx(i) {
        let leftIdx = 2 * i + 1;
        return leftIdx >= this.heap.length ? -1 : leftIdx;
    }
    
    getRightChildIdx(i) {
        let rightIdx = 2 * i + 2;
        return rightIdx >= this.heap.length ? -1 : rightIdx;
    }
    
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
}
class Solution {
public:
    string reorganizeString(string S) {
        // create a map of character to count
        unordered_map counts;
        for (char c : S) {
            counts[c]++;
        }
        
        // create a max heap of characters by count
        priority_queue> pq;
        for (auto& p : counts) {
            pq.push({p.second, p.first});
        }
        
        // build the answer string
        string ans;
        while (!pq.empty()) {
            // get the most frequent character
            auto [count, c] = pq.top();
            pq.pop();
            
            // if this is the first character, append it
            if (ans.empty()) {
                ans += c;
                count--;
            }
            // otherwise, check if the current character can be
            // appended to the end of the answer string
            else if (ans.back() != c) {
                ans += c;
                count--;
            }
            // if not, check if there is another character that can
            // be appended to the end of the answer string
            else if (!pq.empty()) {
                auto [nextCount, nextC] = pq.top();
                pq.pop();
                
                // if so, append it and push the current character
                // back into the heap
                if (nextCount > 0) {
                    ans += nextC;
                    pq.push({count, c});
                }
                // otherwise, return an empty string since there is
                // no way to rearrange the string
                else {
                    return "";
                }
            }
            // if not, return an empty string since there is
            // no way to rearrange the string
            else {
                return "";
            }
            
            // if there are any remaining characters for this
            // character, push it back into the heap
            if (count > 0) {
                pq.push({count, c});
            }
        }
        
        return ans;
    }
};
public class Solution {
    public string ReorganizeString(string S) {
        // Create a count array of the alphabet 
        int[] count = new int[26];
        foreach (char c in S) {
            count[c - 'a']++;
        }
        
        // Create a priority queue to store the characters by their count
        PriorityQueue pq = new PriorityQueue();
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                pq.Add(new CharacterCount((char)(i + 'a'), count[i]));
            }
        }
        
        // Build up the result string
        StringBuilder sb = new StringBuilder();
        while (pq.Count > 1) {
            // Get the two most common characters
            CharacterCount cc1 = pq.Remove();
            CharacterCount cc2 = pq.Remove();
            
            // Append them to the result string
            sb.Append(cc1.c);
            sb.Append(cc2.c);
            
            // Decrement their counts and add them back to the queue
            cc1.count--;
            cc2.count--;
            if (cc1.count > 0) pq.Add(cc1);
            if (cc2.count > 0) pq.Add(cc2);
        }
        
        // If there is still one character left, append it to the end of the string
        if (pq.Count == 1) {
            CharacterCount cc = pq.Remove();
            if (cc.count > 1) return "";
            sb.Append(cc.c);
        }
        
        return sb.ToString();
    }
}

class CharacterCount : IComparable {
    public char c;
    public int count;
    
    public CharacterCount(char c, int count) {
        this.c = c;
        this.count = count;
    }
    
    public int CompareTo(CharacterCount other) {
        return other.count - this.count;
    }
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]