Problem of The Day: Sort Vowels in a String

Problem Statement

leetcode problem link

Brute Force approach [Accepted]

class Solution:
    def sortVowels(self, s: str) -> str:
        vowels = {'a','e','i','o','u'}
        arr = []
        temp = []
        res = list(s)
        for i, c in enumerate(s):
            if c.lower() in vowels:
                arr.append(c)
                temp.append(i)
        arr.sort()

        j = 0
        for i in temp:
            res[i] = arr[j]
            j += 1

        return ''.join(res)

Editorial

Approach 1: Sorting

class Solution {
public:
    // Returns true if the character is a vowel.
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'o'|| c == 'u'|| c == 'i'
            || c == 'A' || c == 'E' || c == 'O'|| c == 'U'|| c == 'I';
    }

    string sortVowels(string s) {
        string temp;

        // Store the vowels in the temporary string.
        for (char c : s) {
            if (isVowel(c)) {
                temp += c;
            }
        }

        // Sort the temporary string characters in ascending order.
        sort(temp.begin(), temp.end());

        int j = 0;
        string ans;
        for (int i = 0; i < s.size(); i++) {
            // If the character is a vowel, replace it with the character in the string temp.
            if (isVowel(s[i])) {
                ans += temp[j];
                j++;
            } else {
                ans += s[i];
            }
        }

        return ans;
    }
};

Approach 2: Counting Sort

class Solution {
public:
    // Returns true if the character is a vowel.
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'o'|| c == 'u'|| c == 'i'
            || c == 'A' || c == 'E' || c == 'O'|| c == 'U'|| c == 'I';
    }

    string sortVowels(string s) {
        unordered_map<char, int> count;

        // Store the frequencies for each character.
        for (char c : s) {
            if (isVowel(c)) {
                count[c]++;
            }
        }

        // Sorted string having all the vowels.
        string sortedVowel = "AEIOUaeiou";
        string ans;
        int j = 0;
        for (int i = 0; i < s.size(); i++) {
            if (!isVowel(s[i])) {
                ans += s[i];
            } else {
                // Skip to the character which is having remaining count.
                while (count[sortedVowel[j]] == 0) {
                    j++;
                }

                ans += sortedVowel[j];
                count[sortedVowel[j]]--;
            }
        }
        return ans;
    }
};