C++ O(n) count freq->bitmask check vowels||15ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nUse vowels="AEIOUaeiou" and string find to count the frequency of each vowel in string 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse `vowels="AEIOUaeiou"` and string `find` to count the frequency of each vowel in string `s`.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThen replace the places in `s` where vowels stand by vowels according the ordering and the `freq`.\n\nThe code is implemented with a linear algorithm, can be furthermore optimized. When the function `isVowel(char c, int idx)` based on `C++ find` is replaced by the function `isVowel0(char c, int idx)` using usual switch-case, the performance is better & runs 18ms beats 99.61%! \n\nThanks to @Sergei, to juduge char `c` can use the following modified bitmask function\n```\n    int freq[53]={0}; //\'u\'-\'A\'=52\n    vector<int> pos;\n    void isVowel_bitMask(char c, int idx){\n        if ((0x208222 >> (c & 0x1f)) & 1){\n            freq[c-\'A\']++;\n            pos.push_back(idx);\n        }\n    }\n``` \nUsing it one can beat 100% with running time 15ms!\n\n# Why bitmask method works?\n\nThe ascii code for `AEIOUaeiou` is\n```\n64+1, 64+5, 64+9, 64+15, 64+16+5,\n64+32+1, 64+32+5, 64+32+9, 64+32+15, 64+32+16+5\n```\nc is a vowel $\\iff$ (c & 0x1f)= 1,5,9,15,21\nand `0x208222=0b1000001000001000100010`\n\nUse the condition `(0x208222 >> (c & 0x1f)) & 1`!!!\n\nLet\'s see the testcase `s="lEetcOde"`\n```\nfreq=[0, 1, 0, 1, 0, 0, 2, 0, 0, 0] \npos=[1, 2, 5, 7]\ns="lEOtcede" \n```\nFor comparison, an implementation using sort is also done.\n\nmethod | freq \uFF06 find | freq & switch-case| sort | bitmask\n--- | --- | --- | --- | ---\nelapsed time |  23ms| **18ms**|   45ms | **15ms**\nbeats | 98.61% | 99.61% |  37.21% | 100%\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code 23ms Beats 98.61%\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:\n    const string vowels="AEIOUaeiou";\n    int freq[10]={0};\n    vector<int> pos;\n    void isVowel(char c, int idx){\n        int i=vowels.find(c);\n        if (i!=-1){\n            freq[i]++;\n            pos.push_back(idx);\n        }\n    }\n    void print(auto & c){\n        for(int i: c) cout<<i<<", ";\n        cout<<endl;\n    }\n\n    string sortVowels(string s) {\n        int n=s.size();\n        #pragma unroll\n        for(int i=0; i<n; i++)\n            isVowel(s[i], i);\n    //    print(pos);\n        int count=0, v=freq[0], j=0;\n        #pragma unroll\n        for (int i: pos){\n            while(count>=v)\n                v+=freq[++j];\n            s[i]=vowels[j];\n            count++;\n        }\n        return s;\n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Code using isVowel0 18ms Beats 99.61%\n```\n    void isVowel0(char c, int idx){\n        switch(c){\n            case \'A\': freq[0]++; pos.push_back(idx); break;\n            case \'E\': freq[1]++; pos.push_back(idx); break;\n            case \'I\': freq[2]++; pos.push_back(idx); break;\n            case \'O\': freq[3]++; pos.push_back(idx); break;\n            case \'U\': freq[4]++; pos.push_back(idx); break;\n            case \'a\': freq[5]++; pos.push_back(idx); break;\n            case \'e\': freq[6]++; pos.push_back(idx); break;\n            case \'i\': freq[7]++; pos.push_back(idx); break;\n            case \'o\': freq[8]++; pos.push_back(idx); break;\n            case \'u\': freq[9]++; pos.push_back(idx); break;\n        }\n    }\n```\n# Code using sort\n\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:\n    string sortVowels(string s) {\n        const string vowels="AEIOUaeiou";\n        string v;\n        vector<int> pos;\n        int n=s.size();\n        #pragma unroll\n        for(int i=0; i<n; i++){\n            if (vowels.find(s[i])!=-1){\n                v.push_back(s[i]);\n                pos.push_back(i);\n            }        \n        }\n        sort(v.begin(), v.end());\n        int count=0;\n        #pragma unroll\n        for(int i:pos){\n            s[i]=v[count++];\n        }\n      \n        return s;\n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Counting Sort', 'Bitmask', 'C++']