[C++] Counting Sort, Time/Space Complexity: O(n)/O(1)
Intuition\n Describe your first thoughts on how to solve this problem. \n- Collect the vowels\n- Replace the vowels in the order\n\n# Approach\n Describe your a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Collect the vowels\n- Replace the vowels in the order\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Use a hash table to check whether a character is a vowel or not\n- Count the number of each vowel\n- Replace the vowels in the nondecreasing order\n\n# Complexity\n- Assume `n = s.size()` and `k = vowels.size()`\n\n- Time complexity: $$O({n}\\times{log(k)}) = O({n}\\times\\log(10)) = O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(k) = O(10) = O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    // time/space: O(n)/O(1)\n    string sortVowels(string s) {\n        // use a hash table to check whether a character is a vowel or not\n        const unordered_set<char> vowels = {\n            \'a\', \'e\', \'i\', \'o\', \'u\',\n            \'A\', \'E\', \'I\', \'O\', \'U\',\n        };\n\n        // count the number of each vowel\n        map<char, int> vowel_count;\n        for (auto& c : s) {\n            if (vowels.count(c) != 0) vowel_count[c]++;\n        }\n\n        // replace the vowels in the nondecreasing order\n        for (char& c : s) {\n            if (vowels.count(c) != 0) {\n                auto it = vowel_count.begin();\n                c = it->first;\n                if (--(it->second) == 0) vowel_count.erase(it);\n            }\n        }\n        return s;\n    }\n};\n```
['Sorting', 'Counting', 'Counting Sort', 'C++']