Leetcode.com problem 2785: "Sort Vowels In String"

Leetcode.com problem 2785: Sort Vowels In String

James S. Plank

Thu Sep 11 18:20:22 EDT 2025

Problem Statement.
Success Rate (as of September, 2025): 83.4%
This is a "medium" problem.
tests.sh: A testing script
answers.txt: Correct output to the testing script
A skeleton with my main() that you can use to test your answer.
solution-1.cpp - A straightforward solution that uses sorting.
solution-2.cpp - A faster solution that uses bit arithmetic and an O(n) algorithm.

In case Leetcode's servers are down

You are to write a method in the class Solution with the following prototype:

string sortVowels(string s);

s is a string composed solely of uppercase and lowercase characters.
s has at most 100,000 characters.
Suppose v is a string composed of the vowels in s, including repetitions.
Now suppose you sort v by ASCII value.
You are to return a string rv[i] with the same size as s.
If s[i] is a consonant, then rv[i] is equal to s[i].
Otherwise, if s[i] is the j-th vowel in s, then s[i] is equal to v[j].
Return rv

The skeleton program

Enter the word on standard input, and it will print the answer on standard output.

Examples

UNIX> echo fedcba | ./a.out
fadcbe                                    # This swaps the 'a' and 'e', since 'a' < 'e'.
UNIX> echo aAeEiIoOuU | ./a.out
AEIOUaeiou                                # Upper case letters have lower ASCII values
UNIX> echo UuUOoOIiIEeEAaE | ./a.out
AEEEIIOOUUaeiou                           # Note how it handles repetitions.
UNIX> echo XUuUOoOIiIEeEAaEY | ./a.out
XAEEEIIOOUUaeiouY
UNIX> echo lEetcOde | ./a.out             # Here are Leetcode's examples
lEOtcede
UNIX> echo lYmpH | ./a.out
lYmpH
UNIX>

The straightfoward solution and its running time

The straightforward way to solve this problem is to be quite literal with it:

Run through the string, and whenever you see a vowel, do two things: (1) Push it onto a vector, v. (2) Set its value in the original string to something that is not a letter, like '-'.
When you're done, sort v.
Set j equal to zero.
Go back through the original string, and wherever you see a '-', substitute it with the j-th character of v, and increment j.
Return the string.

Lets' use "fedcba" as an example. When you run through the string the first, time, you have v = "ea", and the string is "f-dcb-". Now you sort v, so it is "ae". Then you run through the string, and replace the '-' characters with the characters from v in order. So the string becomes "fadcbe".

I have this solution in solution-1.cpp, but I won't put it here, because you should write it for yourself. What's the running time? Well, suppose that every character in s is a vowel. Then creating v will be O(n), but sorting it will be O(n log n). Creating the return value is O(n), so the whole process is O(n log n).

A linear solution and its running time

A different approach is both more efficient and more fun. Maintain a vector called count, of integers. It should have 128 elements, initialized to zero. Whenever s[i] is a vowel, then increment count[s[i]] and set s[i] to '-'. When you're done, count holds the number of occurrences of each vowel, and it was O(n) to create it.

Now, have j equal 'A'. Run through the string again, and when s[i] equals '-', then if count[j] is greater than one, make s[i] equal j and decrement count[j]. When count[j] reaches zero, set j to the next vowel.

Again, this is linear, so your solution is O(n).

I have this solution in solution-2.cpp, but I won't put it here, because you should write it for yourself.

How did they do?

Well, the first solution worked, so that's good. It was only faster than 11 percent of the solutions.

The second solution also worked, but it was faster than 78.8% of the solutions, so paying attention to the running time was a good thing. I could have made this faster by fixing s in place. I instead built up the return value, and that probably added to the running time.

How do you figure out if a character is a vowel?

I used the simple way in my first solution. Have a string x which is equal to "aeiouAEIOU", and then test s[i] with:

if (x.find(s[i]) != string::npos) {    // It's a vowel.

This is more inefficient than it needs to be. You can make it very efficient by realizing that ('z'-'A') is less than 64. Therefore, you can maintain an unsigned long long called mask, such that all of its bits are zero except for ('A'-'A'), ('E'-'A'), ('I'-'A'), ('O'-'A'), etc. Then you can test s[i] with:

  if (mask & (1ULL << (unsigned long long) (s[i]-'A'))) ...

That's a nice efficient O(1) test. This is how solution-2.cpp works. It's a really nice use of bits as sets.