Reorganize String (LC #767)

Hi friends. Today let’s solve problem 767 – Reorganize String.
The problem statement is given a string s, consisting of lowercase English characters, rearrange the characters of s so that any two adjacent characters are not the same. If not possible, return “”.
Examples
1) s = “aab” –> “aba”
2) s = “aaab” –> “”

Intuition:

So from the given examples, first thing we can identify that if max frequency of any letter is greater than half of the string length than we would straight away return empty string. For this we can use below logic.

if(maxFreq > Math.floor(s.length+1)/2)) return "";

Pattern Recognition

So with one requirement out of the way, we are now guaranteed to have the string that can be rearranged in required format. So now the question is how can we do it.

Since the requirement is that we should somehow not have any letter placed next to each other, indicates that we should focus more on max frequency characters than low frequency characters. This sounds like we need to be greedy for max frequency over min frequency. Hence this problem should be solved with greedy approach.

Solution Steps

Now we are ready to layout the steps for solving the problem.

• Loop over string to find frequency of each character and create frequency map.
• If the frequency of most frequent character is more than half of the string, return empty string
• Else we can use the frequency map for building out the result string.
• For building result string, we will create an empty array and will first implant our most frequent character on alternate positions.
• After most frequent characters are placed, we will loop over rest characters and place them on alternating positions.

var reorganizeString = function(s) {
    const freqMap = new Map();
    let maxFreq = 0, maxL = '';
    
    for(let c of s) {
        const freq = freqMap.get(c) || 0;
        freqMap.set(c, freq+1);
        if(freq+1 > maxFreq) {
            maxL = c;
        }
        maxFreq = Math.max(maxFreq, freq+1);
    }
    
    if(maxFreq > Math.floor(s.length+1)/2) return "";
    
    let i = 0, arr = [];
    freqMap.delete(maxL);
    while(maxFreq > 0) {
        arr[i] = maxL;
        i += 2;
        maxFreq--;
        
    }

    for(let [c,f] of freqMap) {
        while(f > 0) {
            if(i >= s.length) i = 1;
            arr[i] = c;
            f--;
            i += 2;
        }
    }
    
    
    return arr.join('');
};