Sort Vowels in a String

Medium

Sort Vowels in a String

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters are considered vowels for this problem (e.g., is 'y' a vowel)? Are we considering both lowercase and uppercase vowels?
Can the input string be empty or null?
Should the output string be the same length as the input string, with non-vowel characters remaining in their original positions?
If there are no vowels in the input string, what should be returned?
Are we expected to preserve the original order of vowels if they are the same (e.g., two 'a's)? If the sorted vowels have duplicates, is that acceptable?

Brute Force Solution

Approach

The brute force method to sort vowels in a string involves finding all the vowels, sorting them separately, and then placing them back into the string. We essentially go through the string multiple times to find, sort, and replace.

Here's how the algorithm would work step-by-step:

First, go through the entire string and identify all the vowels (a, e, i, o, u, and their uppercase versions).
Make a separate collection (like a bag) and put all the vowels you found into it.
Sort the vowels in your collection alphabetically.
Now, go through the original string again, but this time, when you find a vowel, replace it with the next vowel from your sorted collection.
Continue doing this until you've replaced all the vowels in the string with the sorted vowels.

Code Implementation

def sort_vowels_brute_force(input_string):
    vowels = "AEIOUaeiou"
    found_vowels = []

    # Extract all vowels from the input string.
    for char in input_string:
        if char in vowels:
            found_vowels.append(char)

    # Sort the extracted vowels alphabetically.
    found_vowels.sort()

    vowel_index = 0
    result = list(input_string)

    # Replace vowels in the original string with the sorted vowels.
    for index in range(len(result)):
        if result[index] in vowels:
            # Ensures we don't go out of bounds.
            if vowel_index < len(found_vowels):

                # Necessary to modify the list in place.
                result[index] = found_vowels[vowel_index]
                vowel_index += 1

    return "".join(result)

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through the input string of length n to identify all vowels, which takes O(n) time. These vowels are then stored in a separate collection. Sorting this collection of vowels takes O(k log k) time, where k is the number of vowels in the string, and k <= n. Finally, the algorithm iterates through the original string again, replacing vowels with the sorted vowels, taking O(n) time. Since sorting dominates the time complexity, the overall time complexity is O(n + k log k + n), which simplifies to O(n log n) in the worst case when k is proportional to n.

Space Complexity

O(N) – The auxiliary space complexity is determined by the temporary collection used to store the vowels found in the input string. In the worst-case scenario, the input string consists entirely of vowels, requiring the storage of all N characters in this collection. Sorting the vowels in place within the collection does not change the space used. Thus, the space complexity is O(N), where N is the length of the input string.

Optimal Solution

Approach

The best way to sort vowels in a string is to first identify all the vowels and sort them separately. Then, rebuild the string, placing the sorted vowels back into their original positions while keeping the consonants where they were.

Here's how the algorithm would work step-by-step:

First, go through the entire string and pick out all the vowels. Keep these vowels separate from the rest of the string.
Sort the vowels that you've collected in alphabetical order.
Now, go back through the original string, one character at a time.
If the character is a vowel, replace it with the next vowel from your sorted list.
If the character is not a vowel, leave it alone.
By replacing the vowels in order, you create a new string with all the vowels sorted and the consonants in their original places.

Code Implementation

def sort_vowels(input_string):
    vowels = "AEIOUaeiou"
    found_vowels = [character for character in input_string if character in vowels]

    # Sort the found vowels alphabetically.
    found_vowels.sort()

    vowel_index = 0
    result_string_list = list(input_string)

    # Iterate through the string and replace vowels.
    for index, character in enumerate(input_string):
        if character in vowels:

            # Replace with the next sorted vowel.
            result_string_list[index] = found_vowels[vowel_index]
            vowel_index += 1

    # Join the list back into a string.
    return "".join(result_string_list)

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through the string of size n once to extract the vowels, taking O(n) time. The extracted vowels are then sorted, which takes O(k log k) time, where k is the number of vowels and k <= n. Since k is bounded by n, the sorting step is at most O(n log n). Finally, the algorithm iterates through the original string again to reconstruct it with the sorted vowels, taking O(n) time. Therefore, the overall time complexity is O(n) + O(n log n) + O(n), which simplifies to O(n log n).

Space Complexity

O(N) – The algorithm first extracts all vowels into a separate data structure which, in the worst case (a string consisting only of vowels), will require space proportional to the input string length, N. The sorted vowels are then used to rebuild the string. Therefore, the primary space cost comes from storing the extracted vowels, which can grow linearly with the input string size. This results in an auxiliary space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return null or empty string immediately, based on the specific requirements defined in the problem.
String with no vowels	Return the original string unchanged as no vowels need sorting.
String with only one vowel	Return the original string unchanged since a single vowel is already sorted.
String with all vowels and they are already sorted	The algorithm should correctly identify that the vowels are already sorted and return the original string (or a correctly sorted version).
String with all vowels and they are reverse sorted	The algorithm must correctly sort the vowels from reverse order to ascending order.
String with mixed case vowels (e.g., 'aEiou')	Treat uppercase and lowercase vowels differently and sort them accordingly based on their ASCII values or a defined sorting order.
Very long input string (potential memory issues)	If memory is a concern, the algorithm should be optimized to avoid excessive memory allocation, potentially using in-place sorting or streams.
String contains non-ASCII characters	Handle Unicode vowels correctly; either reject non-ASCII input, or extend the vowel set to include appropriate Unicode characters.