[Python] NO SORTING: O(n) time, O(1) space by Counting Occurrences. Better Time Complexty than Sort!
Intuition\n1. There are only 10 vowel characters. In order, they are "A","E","I","O","U","a","e","i","o","u"\n2. Let\'s count the occurrences of each one and st
# Intuition\n1. There are only 10 vowel characters. In order, they are "A","E","I","O","U","a","e","i","o","u"\n2. Let\'s count the occurrences of each one and store that into a 10-element array. This is O(n) time, O(1) space\n3. Then, let\'s use that array to replace all of the vowels in the original string, in order. We will remove counts from our counter array as we do so. This is O(n) time, O(1) space*\n\n*Note that strings are immutable in python and java. So, this problem requires O(n) space for the resulting string for all solutions. I use the term "O(1) space" here because this solution using O(1) auxillary space. If strings were mutable, such as in C++, then this solution could just update $s$ in-place, and thus be a true O(1) space solution (including auxillary and return value).*\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Count the occurrences of each one and store that into an array O(n) time, O(1) space\n2. Use that array to replace all of the vowels in the original string. O(n) time, O(1) space*\n\n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(1)$\n\n# Code\n```py\nclass Solution:\n    def sortVowels(self, s: str) -> str:\n        # Solution 1: Count vowel occurrences -> O(n) time, O(1) auxillary space\n        vowels = ["A","E","I","O","U","a","e","i","o","u"]\n        vowelMap = {"A": 0, "E": 1, "I": 2, "O": 3, "U": 4, "a": 5, "e": 6, "i": 7, "o": 8, "u": 9}\n        def getVIndex(c: str) -> int:\n            if c in vowelMap: return vowelMap[c]\n            return -1\n\n        # step 1) count vowel occurrences in a 10-element array (1 element per unique vowel, case-sensitive)\n        vowelCounts = [0] * 10\n        for i in range(0, len(s)):\n            # use the vowelMap helper to see if a char is a vowel, and to map it to the correct index\n            j = getVIndex(s[i])\n            if j != -1:\n                vowelCounts[j] += 1\n        \n        # step 2) construct result str based on s and vowelCounts array\n        result = ""\n        vowelCountsIndex = 0\n        # simulatenously iterate through our vowel Counts\n        for i in range(0, len(s)):\n            if (getVIndex(s[i])) != -1: # use the vowelMap helper to see if a char is a vowel\n                while (vowelCounts[vowelCountsIndex] < 1):\n                    vowelCountsIndex += 1\n                vowelCounts[vowelCountsIndex] -= 1\n                result = result + vowels[vowelCountsIndex]\n            else: # is a consonant\n                result = result + s[i] \n        \n        return result\n    # note that in python, strings are immutable, so we can\'t turn s into result in-place.\n    # in languages where strings are mutable, e.g. C++, this solution be easy to make O(1)\n    # total space by replacing the chars in s in-place\n```
['Hash Table', 'Iterator', 'Python3']