[Amazon Question] Reorganize String

Problem: Given a string, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result.  If not possible, return the empty string.

Example:

Input: str = "aabc"
Output: "abac"

Approach: Basically here we are using greedy approach. First we build a heap/priority queue of characters of string based on their number of occurrences / frequencies. 

Once we build this heap, we can have a loop till the heap has 2 or more elements. In this loop we do following steps:

• firstMaxChar = heap.Pop()
• secondMaxChar = heap.Pop()
• Append firstMaxChar into result
• Append secondMaxChar into result
• Reduce the frequencies of firstMaxChar and secondMaxChar by 1.
• if frequency of firstMaxChar is more than 0 then add firstMaxChar back to the heap with the reduced frequency
• if frequency of secondMaxChar is more than 0 then add secondMaxChar back to the heap with the reduced frequency

After this loop we can have at max 1 element in the heap. If heap contains an element then we can append this last character to result if it's frequency is 1. If frequency is more than 1 then we know that we can't build the string as we will have repeated neighbors so we should return empty string.

The other simple approach would be to get the character with the maximum frequency and place it first on alternate indices. Now take the other characters and place it in the same way. That's too greedy right but it works :)

Implementation in C#:

Approach 1:

Implementation of Priority Queue is given here,

        public class TupleComparer : IComparer<Tuple<char, int>>

        {

            public int Compare([AllowNull] Tuple<char, int> x, [AllowNull] Tuple<char, int> y)

            {

               return y.Item2 - x.Item2;

            }

        }

        public static string ReorganizeString(string str)

        {

            int[] frequencies = new int[26];

            int uniqueChars = 0;

            foreach (char ch in str)

            {

                if (frequencies[ch - 'a'] == 0)

                {

                    ++uniqueChars;

                }

                ++frequencies[ch - 'a'];

            }

            PriorityQueue<Tuple<char, int>> priorityQueue = new PriorityQueue<Tuple<char, int>>(uniqueChars, new TupleComparer());

            for (int i = 0; i < frequencies.Length; ++i)

            {

                if (frequencies[i] > 0)

                {

                    if (frequencies[i] > (str.Length + 1) / 2)

                    {

                        return string.Empty;

                    }

                    priorityQueue.Push(new Tuple<char, int>((char)('a' + i), frequencies[i]));

                }

            }

            string result = string.Empty;

            while (priorityQueue.Count > 1)

            {

                char firstMaxChar = priorityQueue.Top.Item1;

                priorityQueue.Pop();

                char secondMaxChar = priorityQueue.Top.Item1;

                priorityQueue.Pop();

                result += firstMaxChar;

                result += secondMaxChar;

                --frequencies[firstMaxChar - 'a'];

                if (frequencies[firstMaxChar - 'a'] > 0)

                {

                    priorityQueue.Push(new Tuple<char, int>(firstMaxChar, frequencies[firstMaxChar - 'a']));

                }

                --frequencies[secondMaxChar - 'a'];

                if (frequencies[secondMaxChar - 'a'] > 0)

                {

                    priorityQueue.Push(new Tuple<char, int>(secondMaxChar, frequencies[secondMaxChar - 'a']));

                }

            }

            if (priorityQueue.Count > 0)

            {

                char lastChar = priorityQueue.Top.Item1;

                if (frequencies[lastChar - 'a'] > 1)

                {

                    return string.Empty;

                }

                result += lastChar;

            }

            return result;

        }

Approach 2:

        public string ReorganizeString(string s)

    {

        int maxFreq = 1;

        int[] freqMap = new int[26];

        char maxChar = s[0];

        foreach (char ch in s)

        {

            freqMap[ch - 'a']++;

            if (maxFreq < freqMap[ch - 'a'])

            {

                maxFreq = freqMap[ch - 'a'];

                maxChar = ch;

            }

        }

        if (maxFreq == 1)

        {

            return s;

        }

        if (maxFreq > (s.Length + 1) / 2)

        {

            return string.Empty;

        }

        char[] tempResult = new char[s.Length];

        int writeIndex = 0;

        for (int i = 0; i < maxFreq; ++i)

        {

            tempResult[writeIndex] = maxChar;

            writeIndex += 2;

            --freqMap[maxChar - 'a'];

        }

        for (int i = 0; i < freqMap.Length; ++i)

        {

            while (freqMap[i] > 0)

            {

                if (writeIndex >= s.Length)

                {

                    writeIndex = 1;

                }

                tempResult[writeIndex] = (char)(i + 'a');

                writeIndex += 2;

                --freqMap[i];

            }

        }

        return new string(tempResult);

    }

Complexity: Approach 1: O(nlogn), Approach 2: O(n)