Standard Priority Queue IX: Vowels Frequency

Tally the frequency of the vowels. Push that into a pQueue, the caveat is when the frequencies are the same, you need to keep track of the first occurrence of each vowel and do some math to insert into the priority queue with the right order. After that, it is just dequeuing and inserting into the proper places. Use StringBuilder to avoid unnecessary string allocations.

Code is down below, cheers, ACC.

Sort Vowels by Frequency - LeetCode

You are given a string s consisting of lowercase English characters.

Rearrange only the vowels in the string so that they appear in non-increasing order of their frequency.

If multiple vowels have the same frequency, order them by the position of their first occurrence in s.

Return the modified string.

Vowels are 'a', 'e', 'i', 'o', and 'u'.

The frequency of a letter is the number of times it occurs in the string.

 

Example 1:

Input: s = "leetcode"

Output: "leetcedo"

Explanation:​​​​​​​

• Vowels in the string are ['e', 'e', 'o', 'e'] with frequencies: e = 3, o = 1.
• Sorting in non-increasing order of frequency and placing them back into the vowel positions results in "leetcedo".

Example 2:

Input: s = "aeiaaioooa"

Output: "aaaaoooiie"

Explanation:​​​​​​​

• Vowels in the string are ['a', 'e', 'i', 'a', 'a', 'i', 'o', 'o', 'o', 'a'] with frequencies: a = 4, o = 3, i = 2, e = 1.
• Sorting them in non-increasing order of frequency and placing them back into the vowel positions results in "aaaaoooiie".

Example 3:

Input: s = "baeiou"

Output: "baeiou"

Explanation:

• Each vowel appears exactly once, so all have the same frequency.
• Thus, they retain their relative order based on first occurrence, and the string remains unchanged.

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters

public class Solution {
    public string SortVowels(string s)
    {
        long[] freq = new long[5];
        int[] firstIndex = new int[5];
        for (int i = 0; i < firstIndex.Length; i++)
            firstIndex[i] = -1;
        long MOD = 1000000000000000;

        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            int index = "aeiou".IndexOf(c);
            if (index >= 0)
            {
                freq[index]++;
                if (firstIndex[index] == -1)
                    firstIndex[index] = i;
            }
        }

        PriorityQueue pQueue = new PriorityQueue();
        for (int i = 0; i < freq.Length; i++)
        {
            char c = "aeiou"[i];
            string key = c.ToString() + "@" + freq[i].ToString();
            long priority = freq[i] * 1000000 + (s.Length - firstIndex[i]);
            priority = MOD - priority;
            pQueue.Enqueue(key, priority);
        }

        int sIndex = 0;
        StringBuilder sb = new StringBuilder(s.Length);
        while (pQueue.Count > 0)
        {
            string key = pQueue.Dequeue();
            string[] parts = key.Split('@');
            char c = parts[0][0];
            int count = Int32.Parse(parts[1]);

            while (count > 0)
            {
                if ("aeiou".Contains(s[sIndex]))
                {
                    sb.Append(c);
                    count--;
                }
                else
                {
                    sb.Append(s[sIndex]);
                }
                sIndex++;
            }
        }

        while (sIndex < s.Length)
        {
            sb.Append(s[sIndex]);
            sIndex++;
        }

        return sb.ToString();
    }
}