LeetCode Minimum Swaps to Group All 1's Together Solution
Given a string
s, reverse only all the vowels in the string and return it.
The vowels are
'u', and they can appear in both lower and upper cases, more than once.
s = "hello"
s = "leetcode"
1 <= s.length <= 3 * 105
sconsist of printable ASCII characters.
Problem Link: https://leetcode.com/problems/reverse-vowels-of-a-string/
We will implement two pointers in opposite directions and swap the vowels pointed by the two pointers.
We will start at the two ends of the string
s and move our way into the middle. In each while loop iteration we will check whether
s[r] is a vowel. If both of them are vowels, then we swap the two characters. If not, we will update
r towards the middle by shifting 1 index.
Notice that in the following implementation, we first update
s[l] is a vowel, then proceed to finding
s[r] to be a vowel - this spans over many iterations.
It is also correct to use
while (instead of
if-else) to find the vowels' positions for both pointers, but we will need to check
l < r before swapping (check Valid Palindrome for an implementation example).
1def reverseVowels(self, s: str) -> str: 2 vowels = "aeiouAEIOU" 3 l, r = 0, len(s)-1 4 res = list(s) 5 while l < r: 6 if s[l] not in vowels: # s[l] is not vowel 7 l += 1 8 elif s[r] not in vowels: # s[r] is not vowel 9 r -= 1 10 else: 11 res[l], res[r] = res[r], res[l] # both vowels, swap 12 l += 1 13 r -= 1 14 return "".join(res)