345. Reverse Vowels of a String
Model: qwen2.5-coder:14b
Topics: Two Pointers,String
FAANG asked: 1
Acceptance rate: 45.2%
Problem Breakdown
The problem requires reversing only the vowels in a given string while keeping all other characters in their original positions. The input is a single string s consisting of printable ASCII characters. The output should be the modified string with vowels reversed.
Inputs:
- A string
s(1 <= s.length <= 3 * 10^5)
Outputs:
- A string with all vowels reversed
Implicit Constraints:
- Vowels are ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ and their uppercase counterparts.
- The order of non-vowel characters remains unchanged.
- Edge cases include strings with no vowels, strings with only one vowel, and empty strings.
Intuition
A brute-force approach would involve iterating through the string to identify vowels, storing them in a list, then iterating again to replace the original vowels with those from the reversed list. This approach is inefficient due to its O(n) space complexity for storing vowels and O(n^2) time complexity if not optimized.
The key insight is to use two pointers: one starting at the beginning of the string and the other at the end. Both pointers move towards each other, swapping vowels when both pointers point to vowels. This approach reduces the problem to a single pass through the string, making it more efficient in terms of time and space complexity.
Approach
- Initialize Pointers: Start with two pointers,
leftat the beginning of the string andrightat the end. - Identify Vowels: Create a helper function to check if a character is a vowel.
- Two-Pointer Technique:
- Move the
leftpointer to the right until it points to a vowel. - Move the
rightpointer to the left until it points to a vowel. - Swap the vowels at the
leftandrightpointers. - Increment the
leftpointer and decrement therightpointer.
- Move the
- Repeat: Continue this process until the
leftpointer is no longer less than therightpointer. - Return Result: Convert the list of characters back to a string and return it.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. Each character is processed at most once.
- Space Complexity: O(n), due to the conversion of the string into a list of characters for in-place modification.
Solution
def reverseVowels(s: str) -> str:
def is_vowel(char):
return char.lower() in 'aeiou'
s = list(s)
left, right = 0, len(s) - 1
while left < right:
if not is_vowel(s[left]):
left += 1
elif not is_vowel(s[right]):
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
Edge Cases Handled
- No Vowels: If the string contains no vowels, the pointers will not swap any characters, and the original string is returned.
- Single Vowel: If there’s only one vowel, it remains in its original position since there’s nothing to swap with.
- Empty String: The function handles an empty string by returning it immediately without modification.