Give me 10 minutes - How we think about a solution
Intuition\nTake all vowels first.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/fVv8R93DaTc\n\n\u25A0 Timeline of the video\n\n0:04 Explain a key point of the 
# Intuition\nTake all vowels first.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/fVv8R93DaTc\n\n\u25A0 Timeline of the video\n\n`0:04` Explain a key point of the question\n`1:19` Demonstrate how it works\n`3:09` Coding\n`5:02` Time Complexity and Space Complexity\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 3,055\nMy first goal is 10,000 (It\'s far from done \uD83D\uDE05)\nThank you for your support!\n\n**My channel reached 3,000 subscribers these days. Thank you so much for your support!**\n\n---\n\n# Approach\n\n## How we think about a solution\n\nThe description says "All consonants remain in their original places". So simply if we take only vowels from input string, then rebuild a new string, seems like we can create an answer.\n\n\n---\n\n\u2B50\uFE0F Points\n\nTake only vowels and sort them with reverse order.\n\nWhy reverse sort?\n\nThat\'s because we want to use them from order of small ASCII values. Every time we find a vowel position in the original input string, we want to take one of vowels from a vowel list with `pop`. `pop` is efficient if we take one of vowels from the last position of the list.\n\n\u25A0 ASCII values\n```\n\'A\': 65\n\u2193\n\'Z\': 90\n\n\'a\': 97\n\u2193\n\'z\': 122\n```\nSo, seems like we can do reverse sort as usual.\n\n---\n\nLet\'s see how it works\n\n### How it works\n\n```\nInput: s = "lEetcOde"\n```\n- Step 1: Collect vowels and sort them in descending order\n\nAll vowels are `E` `e` `O` `e`. Sort them with reverse order.\n```\nvowels_sorted = [\'e\', \'e\', \'O\', \'E\']\n```\n\n- Step 2: Construct the answer string by replacing vowels in sorted order\n\nIterate through input string one by one from beginning to the last\n\n```\n"lEetcOde"\n \u2191\n\nNo vowel position, just add "l" to res\nres = ["l"]\nvowels_sorted = [\'e\', \'e\', \'O\', \'E\']\n```\n```\n"lEetcOde"\n  \u2191\n\nFound vowel position, pop one of sorted vowels from the last(= "E")\nres = ["l","E"]\nvowels_sorted = [\'e\', \'e\', \'O\']\n```\n```\n"lEetcOde"\n   \u2191\n\nFound vowel position, pop one of sorted vowels from the last(= "O")\nres = ["l","E","O"]\nvowels_sorted = [\'e\', \'e\']\n```\n```\n"lEetcOde"\n    \u2191\n\nNo vowel position, just add "t" to res\nres = ["l","E","O","t"]\nvowels_sorted = [\'e\', \'e\']\n```\n```\n"lEetcOde"\n     \u2191\n\nNo vowel position, just add "c" to res\nres = ["l","E","O","t","c"]\nvowels_sorted = [\'e\', \'e\']\n```\n```\n"lEetcOde"\n      \u2191\n\nFound vowel position, pop one of sorted vowels from the last(= "e")\nres = ["l","E","O","t","c","e"]\nvowels_sorted = [\'e\']\n```\n```\n"lEetcOde"\n       \u2191\n\nNo vowel position, just add "d" to res\nres = ["l","E","O","t","c","e","d"]\nvowels_sorted = [\'e\']\n```\n```\n"lEetcOde"\n        \u2191\n\nFound vowel position, pop one of sorted vowels from the last(= "e")\nres = ["l","E","O","t","c","e","d","e"]\nvowels_sorted = []\n```\n\n- Step 3: Join the characters to form the final string\n\nNow res is array. Connect all characters with no space.\n```\nreturn \'\'.join(result)\n```\n```\nOutput: "lEOtcede"\n```\n\nEasy\uFF01\uD83D\uDE06\n\nLet\'s see a real algorithm!\n\n\n---\n\n\n\n### Algorithm Overview:\n\n1. Collect Vowels and Sort\n2. Construct the Answer String\n3. Join Characters to Form Final String\n   \n\n### Detailed Explanation:\n\n1. **Collect Vowels and Sort:**\n   ```python\n   vowels_sorted = sorted([c for c in s if c.lower() in \'aeiou\'], reverse=True)\n   ```\n   - Create a list comprehension to iterate through each character `c` in the input string `s`.\n   - Check if the lowercase version of `c` is a vowel.\n   - Add vowels to the list `vowels_sorted`.\n   - Sort the list `vowels_sorted` in descending order.\n\n2. **Construct the Answer String:**\n   ```python\n   result = []\n   for char in s:\n       if char.lower() in \'aeiou\':\n           result.append(vowels_sorted.pop())\n       else:\n           result.append(char)\n   ```\n   - Initialize an empty list `result` to store the characters of the final string.\n   - Iterate through each character `char` in the input string `s`.\n   - Check if `char` is a vowel.\n   - If it is a vowel, pop the last vowel from `vowels_sorted` and append it to the result list.\n   - If it is not a vowel, append the character `char` to the result list.\n\n3. **Join Characters to Form Final String:**\n   ```python\n   return \'\'.join(result)\n   ```\n   - Use the `join` method to concatenate the characters in the result list into a single string.\n   - Return the final string as the result.\n\nThis algorithm maintains the original order of consonants while sorting vowels in the non-decreasing order of their ASCII values.\n\n\n\n\n\n# Complexity\n- Time complexity: $$O(n log n)$$\n\n    Step 1: Sorting vowels - $$O(n log n)$$\n    Step 2: Constructing answer string - $$O(n)$$\n    Step 3: Joining characters - $$O(n)$$\n\n\n- Space complexity: $$O(n)$$\n\n    Sorted vowels list - $$O(n)$$\n    Answer string - $$O(n)$$\n\n```python []\nclass Solution:\n    def sortVowels(self, s: str) -> str:\n        # Step 1: Collect vowels and sort them in descending order\n        vowels_sorted = sorted([c for c in s if c.lower() in \'aeiou\'], reverse=True)\n\n        # Step 2: Construct the answer string by replacing vowels in sorted order\n        result = []\n        for char in s:\n            if char.lower() in \'aeiou\':\n                result.append(vowels_sorted.pop())\n            else:\n                result.append(char)\n\n        # Step 3: Join the characters to form the final string\n        return \'\'.join(result)\n```\n```javascript []\n/**\n * @param {string} s\n * @return {string}\n */\nvar sortVowels = function(s) {\n    // Step 1: Collect vowels and sort them in descending order\n    const vowelsSorted = [...s].filter(c => \'aeiouAEIOU\'.includes(c)).sort().reverse();\n\n    // Step 2: Construct the answer string by replacing vowels in sorted order\n    let result = \'\';\n    for (const char of s) {\n        if (\'aeiouAEIOU\'.includes(char)) {\n            result += vowelsSorted.pop();\n        } else {\n            result += char;\n        }\n    }\n\n    // Step 3: Return the final string\n    return result;    \n};\n```\n```java []\nclass Solution {\n    public String sortVowels(String s) {\n        // Step 1: Collect vowels and sort them in descending order\n        List<Character> vowels = new ArrayList<>();\n        for (char c : s.toCharArray()) {\n            if ("aeiouAEIOU".indexOf(c) != -1) {\n                vowels.add(c);\n            }\n        }\n        Collections.sort(vowels, Collections.reverseOrder());\n\n        // Step 2: Construct the answer string by replacing vowels in sorted order\n        StringBuilder result = new StringBuilder();\n        for (char c : s.toCharArray()) {\n            if ("aeiouAEIOU".indexOf(c) != -1) {\n                result.append(vowels.get(vowels.size() - 1));\n                vowels.remove(vowels.size() - 1);\n            } else {\n                result.append(c);\n            }\n        }\n\n        // Step 3: Return the final string\n        return result.toString();        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    string sortVowels(string s) {\n        // Step 1: Collect vowels and sort them in descending order\n        vector<char> vowels;\n        for (char c : s) {\n            if (string("aeiouAEIOU").find(c) != string::npos) {\n                vowels.push_back(c);\n            }\n        }\n        sort(vowels.begin(), vowels.end(), greater<char>());\n\n        // Step 2: Construct the answer string by replacing vowels in sorted order\n        string result;\n        for (char c : s) {\n            if (string("aeiouAEIOU").find(c) != string::npos) {\n                result += vowels.back();\n                vowels.pop_back();\n            } else {\n                result += c;\n            }\n        }\n\n        // Step 3: Return the final string\n        return result;        \n    }\n};\n```\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u25A0 Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n\u25A0 Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/bus-routes/solutions/4279742/video-give-me-10-minutes-beats-9953-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/LcJYpE92UHs\n\n\u25A0 Timeline of the video\n\n`0:03` Explain difficulty and a key point of the question\n`1:31` Demonstrate how it works\n`4:08` Coding\n`10:15` Time Complexity and Space Complexity
['C++', 'Java', 'Python3', 'JavaScript']