[C++] Sorting Vs. Linear Time and Constant Space Approach, 15ms, 10.72MB
All that this problem is asking us is basically to:\n collect all the vowels in s;\n sort them;\n put them back in s in their newly sorted order.\n\nTo do so, w
All that this problem is asking us is basically to:\n* collect all the vowels in `s`;\n* sort them;\n* put them back in `s` in their newly sorted order.\n\nTo do so, we will start by declaring a few support variables:\n* `len` will store the length of `s`;\n* `w` will be our writing pointer to write the vowels from and back into `s`;\n* `vowels` is an array of `len` (the maximum amount we can possibly take) characters.\n\nWe will then loop through every character `c` in `s` and, when it is a vowel, we will:\n* write `c` in `vowels[w]`;\n* increase `w` by `1`.\n\nNext, we will sort the first `w` elements in `vowels` and then reset `w` to be `0`, ready to write the vowels back!\n\nIn our second loop we are this time taking `c` as a refence and every time we will match a vowel, we will:\n* write the content of `vowels[w]` in `c`;\n* increase `w` by `1`.\n\nOnce done, we can `return` `s`.\n\n# Complexity\n- Time complexity: $$O(n log(n))$$\n- Space complexity: $$O(n)$$\n\n# Code\n```cpp\nclass Solution {\npublic:\n    string sortVowels(string s) {\n        int len = s.size(), w = 0;\n        char vowels[len];\n        for (char c: s) {\n            if (c == \'a\' || c == \'e\' || c == \'i\' || c == \'o\' || c == \'u\' || c == \'A\' || c == \'E\' || c == \'I\' || c == \'O\' || c == \'U\') {\n                vowels[w++] = c;\n            }\n        }\n        sort(vowels, vowels + w);\n        w = 0;\n        for (char &c: s) {\n            if (c == \'a\' || c == \'e\' || c == \'i\' || c == \'o\' || c == \'u\' || c == \'A\' || c == \'E\' || c == \'I\' || c == \'O\' || c == \'U\') {\n                c = vowels[w++];\n            }\n        }\n        return s;\n    }\n};\n```\n\n# Complexity\n- Time complexity: $$O(n))$$\n- Space complexity: $$O(1)$$\n\n# Code\nBut we can avoid (common) sorting if we just count the frequence of each vowel in `vowels` (now a reference string) initially, storing them in `freqs` and knowing the first position would match `\'A\'`, the second `\'E\'` and so on.\n\nThis bit is basically bucket sorting in disguise.\n\nIn our second loop, every time we are going to match a vowel, we are going to:\n* move the pointer `w` forward, until we find a bucket in `freqs` with value `!= 0`;\n* next we will again write `vowels[w]` in `c`;\n* finally, we are going to decrease the frequency of the current vowel (ie: `freqs[w]`) by `1`.\n\n```cpp\nclass Solution {\npublic:\n    string sortVowels(string s) {\n        // support variables\n        int len = s.size(), w = 0, freqs[10] = {};\n        string vowels = "AEIOUaeiou";\n        // populating freqs\n        for (char c: s) {\n            auto pos = vowels.find(c);\n            if (pos != -1) freqs[pos]++;\n        }\n        // putting back sorted vowels in s\n        for (char &c: s) {\n            if (c == \'a\' || c == \'e\' || c == \'i\' || c == \'o\' || c == \'u\' || c == \'A\' || c == \'E\' || c == \'I\' || c == \'O\' || c == \'U\') {\n                // looking for the next available vowel\n                while (!freqs[w]) w++;\n                // adding the next available vowels back\n                c = vowels[w];\n                // removing the used vowel from the count\n                freqs[w]--;\n            }\n        }\n        return s;\n    }\n};\n```
['Sorting', 'Bucket Sort', 'C++']