Problem Description

You are given a 0-indexed string s. Your task is to rearrange (permute) the characters in s to create a new string t with the following rules:

1. Consonants stay in place: Any character that is a consonant must remain at its original position. If s[i] is a consonant, then t[i] = s[i].

2. Vowels are sorted: All vowels in the string must be rearranged so they appear in non-decreasing order by their ASCII values. The vowels should fill the positions where vowels originally existed in s, but now sorted from smallest to largest ASCII value.

The vowels are defined as 'a', 'e', 'i', 'o', and 'u' (both lowercase and uppercase versions). All other letters are consonants.

For example, if you have a string with vowels at positions 1, 3, and 5, you would:

• Extract all the vowels from the string
• Sort these vowels by their ASCII values
• Place the sorted vowels back into positions 1, 3, and 5 (where vowels originally were)
• Keep all consonants in their original positions

The solution approach involves:

1. Collecting all vowels from the string into a separate list vs
2. Sorting this list of vowels
3. Creating a copy of the original string as a list
4. Iterating through the string and replacing each vowel position with the next vowel from the sorted list
5. Joining the result back into a string

Intuition

The key insight is that we need to handle vowels and consonants separately. Since consonants must remain in their original positions, we can think of them as "fixed" elements. The vowels, on the other hand, need to be rearranged among themselves.

When we need to sort only specific elements while keeping others fixed, a natural approach is to:

1. Extract the elements that need sorting
2. Sort them independently
3. Put them back in their designated positions

Think of it like having a bookshelf where some books (consonants) are glued in place, while others (vowels) can be moved. To sort the moveable books alphabetically, we would:

• Take out all the moveable books
• Sort them on a table
• Put them back into the empty slots in order

The ASCII value sorting requirement tells us we need to consider both uppercase and lowercase letters. Since uppercase letters have smaller ASCII values than lowercase ones (e.g., 'A' = 65 < 'a' = 97), when we sort the vowels, uppercase vowels will naturally come before lowercase ones.

This leads us to a two-pass solution:

• First pass: collect all vowels and sort them
• Second pass: traverse the string again, replacing vowels with sorted ones in order while keeping consonants unchanged

The beauty of this approach is its simplicity - we don't need complex in-place swapping or tracking multiple pointers. We just extract, sort, and replace.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a straightforward extract-sort-replace pattern:

Step 1: Extract Vowels

vs = [c for c in s if c.lower() in "aeiou"]

We use a list comprehension to iterate through the string s and collect all vowels. The condition c.lower() in "aeiou" cleverly handles both uppercase and lowercase vowels by converting each character to lowercase for the check, but storing the original character in the list.

Step 2: Sort the Vowels

vs.sort()

We sort the vowels list in-place. Python's sort uses ASCII values by default, so uppercase letters (ASCII 65-90) will come before lowercase letters (ASCII 97-122). For example, ['e', 'A', 'o'] becomes ['A', 'e', 'o'].

Step 3: Create a Mutable Copy

cs = list(s)

Since strings are immutable in Python, we convert the string to a list of characters that we can modify.

Step 4: Replace Vowels in Order

j = 0
for i, c in enumerate(cs):
    if c.lower() in "aeiou":
        cs[i] = vs[j]
        j += 1

We traverse the character list with index i. When we encounter a vowel (checked the same way as in Step 1), we replace it with the next sorted vowel from vs using pointer j. The pointer j ensures we use sorted vowels in order. Consonants remain untouched as we only modify positions where vowels exist.

Step 5: Build the Result

return "".join(cs)

Finally, we join the character list back into a string and return it.

The time complexity is O(n log n) due to sorting the vowels, where n is the length of the string. The space complexity is O(n) for storing the vowels list and the character list.

Example Walkthrough

Let's walk through the solution with the string s = "lEetcOde".

Step 1: Extract Vowels We identify and collect all vowels from the string:

• Position 1: 'E' (vowel)
• Position 2: 'e' (vowel)
• Position 5: 'O' (vowel)
• Position 6: 'd' (consonant)
• Position 7: 'e' (vowel)

Extracted vowels: vs = ['E', 'e', 'O', 'e']

Step 2: Sort the Vowels Sort by ASCII values:

• 'E' (ASCII 69) < 'O' (ASCII 79) < 'e' (ASCII 101) < 'e' (ASCII 101)

Sorted vowels: vs = ['E', 'O', 'e', 'e']

Step 3: Create a Mutable Copy Convert string to list: cs = ['l', 'E', 'e', 't', 'c', 'O', 'd', 'e']

Step 4: Replace Vowels in Order Traverse the list and replace vowels with sorted ones:

• i=0: 'l' is consonant → keep 'l'
• i=1: 'E' is vowel → replace with vs[0]='E' → ['l', 'E', 'e', 't', 'c', 'O', 'd', 'e']
• i=2: 'e' is vowel → replace with vs[1]='O' → ['l', 'E', 'O', 't', 'c', 'O', 'd', 'e']
• i=3: 't' is consonant → keep 't'
• i=4: 'c' is consonant → keep 'c'
• i=5: 'O' is vowel → replace with vs[2]='e' → ['l', 'E', 'O', 't', 'c', 'e', 'd', 'e']
• i=6: 'd' is consonant → keep 'd'
• i=7: 'e' is vowel → replace with vs[3]='e' → ['l', 'E', 'O', 't', 'c', 'e', 'd', 'e']

Step 5: Build the Result Join the characters: "lEOtcede"

The consonants 'l', 't', 'c', 'd' stayed in positions 0, 3, 4, 6 respectively, while the vowels were rearranged in sorted order across positions 1, 2, 5, 7.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm consists of the following steps:

1. Extract vowels from the string by iterating through all n characters - O(n)
2. Sort the extracted vowels using Python's built-in sort - O(k × log k) where k is the number of vowels, and in the worst case k = n, so this becomes O(n × log n)
3. Convert the original string to a list - O(n)
4. Iterate through the list and replace vowels with sorted vowels - O(n)
5. Join the list back into a string - O(n)

The dominant operation is the sorting step with O(n × log n) complexity, making the overall time complexity O(n × log n).

Space Complexity: O(n)

The algorithm uses additional space for:

1. List vs to store vowels - in the worst case, all characters are vowels, so O(n)
2. List cs which is a copy of the original string - O(n)
3. The output string created by join - O(n)

Therefore, the total space complexity is O(n), where n is the length of the input string s.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling Case Sensitivity

A common mistake is forgetting that uppercase and lowercase vowels have different ASCII values, with uppercase letters having smaller ASCII values than lowercase ones.

Pitfall Example:

# Incorrect: This would sort alphabetically ignoring case
vowels.sort(key=str.lower)  # 'A' and 'a' would be treated as equal

Why it's wrong: The problem specifically asks to sort by ASCII values. 'A' (ASCII 65) should come before 'a' (ASCII 97), but using key=str.lower would treat them as equivalent and maintain their original relative order.

Correct Approach:

vowels.sort()  # Default sort uses ASCII values

2. Modifying the String Directly

Attempting to modify the string in-place without converting it to a mutable data structure.

Pitfall Example:

# Incorrect: Strings are immutable in Python
for i in range(len(s)):
    if s[i].lower() in "aeiou":
        s[i] = vowels[vowel_index]  # TypeError: 'str' object does not support item assignment

Correct Approach:

characters = list(s)  # Convert to mutable list first
for i in range(len(characters)):
    if characters[i].lower() in "aeiou":
        characters[i] = vowels[vowel_index]

3. Using Set for Vowel Check Without Considering Performance

While using a set for vowel checking seems more efficient, for small fixed sets like vowels, the string membership test is actually comparable or faster.

Alternative (not necessarily better):

VOWELS = set('aeiouAEIOU')
if char in VOWELS:  # Slightly different approach

Why the original is fine: For a 10-character string like "aeiouAEIOU", Python's string membership test is optimized and performs well. The char.lower() in "aeiou" approach is also more readable and handles both cases elegantly.

4. Forgetting to Track the Vowel Index

Missing or incorrectly updating the index for the sorted vowels list.

Pitfall Example:

# Incorrect: Using the same index for both arrays
for i in range(len(characters)):
    if characters[i].lower() in "aeiou":
        characters[i] = vowels[i]  # Wrong! Should use separate index

Correct Approach:

vowel_index = 0
for i in range(len(characters)):
    if characters[i].lower() in "aeiou":
        characters[i] = vowels[vowel_index]
        vowel_index += 1  # Don't forget to increment!