Sort Vowels in a String

The solution is quite easy to flesh out. First, we need a function to decipher whether a character is a vowel or not.

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
        || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}

Then, we want to keep track of the indices of all the vowels inside the string s so we define vowelIndices so that we know where to place them after sorting the vowels.

vector<int> vowelIndices;

Now, since we know the sorted vowels will always be sorted in the same order (AEIOUaeiou), we can simply record the frequency of each vowel...

for (int i = 0; i < s.size(); ++i) {
    if (isVowel(s[i])) {
        ++mp[s[i]];
        vowelIndices.push_back(i);
    }
}

...and then place them in their newly appointed index.

string vowelOrder = "AEIOUaeiou";
int index = 0;
for (int i = 0; i < vowelIndices.size(); ++i) {
    while (mp[vowelOrder[index]] == 0) {
        ++index;
    }
    s[vowelIndices[i]] = vowelOrder[index];
    --mp[vowelOrder[index]];
}

Now, we can simply return the newly sorted s.

return s;

code

class Solution {
public:
    string sortVowels(string s) {
        unordered_map<char, int> mp;
        vector<int> vowelIndices;
        for (int i = 0; i < s.size(); ++i) {
            if (isVowel(s[i])) {
                ++mp[s[i]];
                vowelIndices.push_back(i);
            }
        }

        string vowelOrder = "AEIOUaeiou";
        int index = 0;
        for (int i = 0; i < vowelIndices.size(); ++i) {
            while (mp[vowelOrder[index]] == 0) {
                ++index;
            }
            s[vowelIndices[i]] = vowelOrder[index];
            --mp[vowelOrder[index]];
        }
        return s;
    }
private:
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
            || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }
};

complexity

• Time: O(n)
• Space: O(n)

time taken

• 5 minutes and 50 seconds