✅ Beats 100% -Explained with [ Video ] - Modified Counting Sort
\n\n\n# YouTube Video Explanation\nhttps://youtu.be/5OK2Kqlfo0o\n\n\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making co
\n![Screenshot 2023-11-13 101443.png](https://assets.leetcode.com/users/images/7b7e54f2-5af7-482f-a315-730f5bbfd6ec_1699851095.6065238.png)\n\n# YouTube Video Explanation\n[https://youtu.be/5OK2Kqlfo0o](https://youtu.be/5OK2Kqlfo0o)\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Current Subscribers: 237*\n*Subscribe Goal: 250 Subscribers*\n\n# Example Explanation\nLet\'s break down the solution step by step using tables to visualize the process:\n\n### Example:\n\nGiven String: "lEetcOde"\n\n#### Initialization:\n\n| Char | ASCII | Vowel Count | Count Index Map |\n|------|-------|-------------|-----------------|\n| \'A\'  | 65    | 0           | 1               |\n| \'E\'  | 69    | 0           | 2               |\n| \'I\'  | 73    | 0           | 3               |\n| \'O\'  | 79    | 0           | 4               |\n| \'U\'  | 85    | 0           | 5               |\n| \'a\'  | 97    | 0           | 6               |\n| \'e\'  | 101   | 0           | 7               |\n| \'i\'  | 105   | 0           | 8               |\n| \'o\'  | 111   | 0           | 9               |\n| \'u\'  | 117   | 0           | 10              |\n\n#### Iteration through String \'lEetcOde\':\n\n| Char | ASCII | Vowel Count | Count Index Map |\n|------|-------|-------------|-----------------|\n| \'l\'  | 108   | 0           | 0               |\n| \'E\'  | 69    | 1           | 2               |\n| \'e\'  | 101   | 1           | 7               |\n| \'t\'  | 116   | 0           | 0               |\n| \'c\'  | 99    | 0           | 0               |\n| \'O\'  | 79    | 1           | 4               |\n| \'d\'  | 100   | 0           | 0               |\n| \'e\'  | 101   | 2           | 7               |\n\n#### Rearranging Vowels in Result:\n\n| Char | ASCII | Vowel Count | Count Index Map |\n|------|-------|-------------|-----------------|\n| \'l\'  | 108   | 0           | 0               |\n| \'E\'  | 69    | 0           | 2               |\n| \'O\'  | 79    | 0           | 4               |\n| \'e\'  | 101   | 0           | 7               |\n| \'t\'  | 116   | 0           | 0               |\n| \'c\'  | 99    | 0           | 0               |\n| \'d\'  | 100   | 0           | 0               |\n| \'e\'  | 101   | 0           | 7               |\n\n#### Resultant String:\n\n"lEOtcede"\n\n\n# Intuition\nThe problem involves rearranging the characters of the given string `s` based on specific rules related to vowels and consonants. Vowels must be sorted in non-decreasing order of their ASCII values, while consonants remain in their original places. The solution likely employs a counting and mapping approach to achieve the desired rearrangement.\n\n# Approach\n\n1. Initialize arrays to count the occurrences of vowels (`vowelCount`) and to map the ASCII values of characters (`countIndexMap`). These arrays help in determining the positions of vowels in the rearranged string.\n\n2. Iterate through the characters of the input string `s`:\n   - For each vowel encountered, update the `vowelCount` array.\n   - Populate the `countIndexMap` array to map each character to its ASCII value.\n\n3. Iterate through the `vowelCount` array to rearrange the vowels in the result string (`result`). Update the characters in the `result` array based on the count of each vowel, ensuring they are sorted according to their ASCII values.\n\n4. Return the final string obtained after rearranging both vowels and consonants.\n\n\n- Time Complexity: O(N)\n  - The algorithm iterates through the input string `s` once, and the subsequent iteration through the `vowelCount` array takes constant time.\n  \n- Space Complexity: O(1)\n  - The additional space used is independent of the input size, making it constant space. The arrays (`vowelCount` and `countIndexMap`) have fixed sizes.\n\n\n# Code\n## Java\n```\npublic class Solution {\n    public String sortVowels(String s) {\n        int[] vowelCount = new int[11];\n        int[] countIndexMap = new int[128];\n        char[] result = s.toCharArray();\n        char[] charMap = "AEIOUaeiou".toCharArray();\n\n        for (int i = 0; i < charMap.length; i++) \n            countIndexMap[charMap[i]] = i + 1;\n\n        for (char c : result) \n            vowelCount[countIndexMap[c]]++;\n        int j = 1;\n        int i = 0;\n\n        while (j < vowelCount.length) {\n            if (vowelCount[j] > 0)\n                while (i < result.length) {\n                    if (countIndexMap[result[i]] == 0) {\n                        i++;\n                        continue;\n                    }\n                    vowelCount[j]--;\n                    result[i++] = charMap[j - 1];\n                    break;\n                }\n            else\n                j++;  \n        }\n        return new String(result);\n    }\n}\n```\n## C++\n```\nclass Solution {\npublic:\n    bool isVowel(char ch){\n        if(ch==\'a\' || ch==\'e\' || ch==\'i\' || ch==\'o\' || ch==\'u\' ||\n        ch==\'A\' || ch==\'E\' || ch==\'I\' || ch==\'O\' || ch==\'U\')return true;\n\n        return false;\n    }\n    string sortVowels(string s) {\n        int freq[128]={0};\n\n        for(int i=0;i<s.size();i++){\n            if(isVowel(s[i]))freq[(int)s[i]]++;\n        }\n\n        int idx=0;\n        for(int i=0;i<s.size();i++){\n            if(isVowel(s[i])){\n                while(freq[idx]==0)idx++;\n                s[i]=(char)idx;\n                freq[idx]--;\n            }\n        }\n\n        return s;\n    }\n};\n```\n## Python3\n```\nclass Solution:\n    def sortVowels(self, s: str) -> str:\n        vowels = [\'A\', \'E\', \'I\', \'O\', \'U\', \'a\', \'e\', \'i\', \'o\', \'u\']\n        count_char = Counter(s)\n        s_vowels = []\n        for char in count_char.keys():\n            if char in vowels:\n                s_vowels.append(char)                \n                s = s.replace(char, \'_\')                              \n        s_vowels.sort()\n        for char in s_vowels:\n            s = s.replace(\'_\', char, count_char[char])\n        return s\n```\n## JavaScript\n```\nvar sortVowels = function(s) {\n    const vowels = "AEIOUaeiou"\n    const count = new Array(vowels.length).fill(0)\n    for (let char of s) {\n        const index = vowels.indexOf(char)\n        if (index !== -1) {\n            count[index]++\n        }\n    }\n    let str = ""\n    let curr = 0\n    for (let char of s) {\n        if (vowels.includes(char)) {\n            while (count[curr] === 0) {\n                curr++\n            }\n\n            str += vowels[curr]\n            count[curr]--\n        } else {\n            str += char\n        }\n    }\n    return str\n};\n```\n![upvote1.jpeg](https://assets.leetcode.com/users/images/efdb182c-8478-4288-9d9e-69032a2a8306_1699851020.2164738.jpeg)
['String', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']