C++ | Beats 99.25% | Step By Step Explanation
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe code sorts the vowels in the input string while preserving the order of conso
\n![image.png](https://assets.leetcode.com/users/images/ad5be7b5-529a-430e-bc33-cd52bb6f14be_1712521879.5760655.png)\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe code sorts the vowels in the input string while preserving the order of consonants. It achieves this by first counting the occurrences of vowels in both uppercase and lowercase. Then, it constructs a sorted string of vowels, both uppercase and lowercase. Finally, it iterates through the input string, replacing each vowel with the corresponding sorted vowel from the temporary string, while leaving consonants unchanged. This approach maintains the original order of consonants while sorting the vowels.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n### Approach:\n\n1. **Counting Vowels**:\n    - Initialize two vectors, `upper` and `lower`, to count the occurrences of vowels in uppercase and lowercase respectively.\n    - Iterate through the input string `s`, checking each character to see if it\'s a vowel in either uppercase or lowercase, and increment the corresponding count in the respective vector.\n\n2. **Constructing Sorted Vowel String**:\n    - After counting the occurrences of vowels, construct a temporary string `temp`.\n    - Iterate through both vectors (`upper` and `lower`) and construct the sorted string of vowels.\n    - Append the vowels in alphabetical order, first uppercase and then lowercase.\n\n3. **Replacing Vowels in Input String**:\n    - Initialize two pointers, `start1` and `start2`, to traverse the original input string `s` and the temporary string `temp` respectively.\n    - Initialize `end1` and `end2` as the end indices of `s` and `temp` respectively.\n    - Traverse the input string `s`.\n    - For each character in `s`, if it\'s a vowel, replace it with the corresponding vowel from the sorted string `temp`, incrementing `start2` to move to the next character in `temp`.\n    - If the character in `s` is not a vowel, directly append it to the result string `ans`.\n    - This process continues until all characters in `s` are processed.\n\n4. **Returning the Result**:\n    - Once all characters in `s` are processed, return the resulting string `ans`, which contains the sorted vowels and the original consonants in their respective positions.\n\n\n# Complexity\n#### Time Complexity: O(n)\n- Counting Vowels: The loop iterating over the input string s runs in O(n) time, where n is the length of the input string.\n- Constructing Sorted Vowel String: The loop iterating over the vectors upper and lower to construct the sorted string of vowels also runs in O(n) time because it iterates over all characters in the string.\n- Replacing Vowels in Input String: The loop traversing the input string s to replace vowels with the corresponding sorted vowels from the temporary string temp also runs in O(n) time.\n- Overall, the time complexity is O(n), where n is the length of the input string.\n\n### Space Complexity: O(n)\n- Counting Vowels: Two vectors upper and lower of size 26 are used to count the occurrences of vowels in uppercase and lowercase respectively. Therefore, the space complexity for this step is O(1).\n- Constructing Sorted Vowel String: A temporary string temp is used to store the sorted vowels, which can have a maximum length of 10 (5 uppercase + 5 lowercase vowels). Therefore, the space complexity for this step is O(1).\n- Replacing Vowels in Input String: An additional string ans is used to store the result. The space complexity for this step is O(n), where n is the length of the input string.\n- Overall, the space complexity is O(n) due to the space required for the result string ans.\n\n# Code\n```\nauto init =[]()\n{\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n\nclass Solution {\npublic:\n    string sortVowels(string s) {\n        vector<int> upper(26, 0);\n        vector<int> lower(26, 0);\n\n        for(int i=0; i<s.size(); i++){\n            if(s[i] == \'A\' || s[i] == \'E\' || s[i] == \'I\' || s[i] == \'O\' || s[i] == \'U\'){\n                upper[s[i] - \'A\']++;\n            }\n        }\n        for(int i=0; i<s.size(); i++){\n            if(s[i] == \'a\' || s[i] == \'e\' || s[i] == \'i\' || s[i] == \'o\' || s[i] == \'u\'){\n                lower[s[i] - \'a\']++;\n            }\n        }\n\n        string temp = "";\n\n        for(int i=0; i<26; i++){\n            char ch = i + \'A\';\n            while(upper[i]){\n                temp += ch;\n                upper[i]--;\n            }\n        }\n\n        for(int i=0; i<26; i++){\n            char ch = i + \'a\';\n            while(lower[i]){\n                temp += ch;\n                lower[i]--;\n            }\n        }\n\n        int start1 = 0;\n        int end1 = s.size()-1;\n\n        int start2 = 0;\n        int end2 = temp.size()-1;\n\n\n        string ans = "";\n\n        while(start1 <= end1 || start2 <= end2){\n            if(s[start1] == \'A\' || s[start1] == \'E\' || s[start1] == \'I\' || s[start1] == \'O\' || s[start1] == \'U\' || s[start1] == \'a\' || s[start1] == \'e\' || s[start1] == \'i\' || s[start1] == \'o\' || s[start1] == \'u\'){\n                ans += temp[start2];\n                start2++;\n            }\n            else{\n                ans += s[start1];\n            }\n            start1++;\n        }\n        return ans;\n    }\n};\n```
['String', 'Sorting', 'C++']