Minimum Swaps to Group All 1's Together
Given a string s
, reverse only all the vowels in the string and return it.
The vowels are 'a'
, 'e'
, 'i'
, 'o'
, and 'u'
, and they can appear in both lower and upper cases, more than once.
Example 1:
Input: s = "hello"
Output: "holle"
Example 2:
Input: s = "leetcode"
Output: "leotcede"
Constraints:
1 <= s.length <= 3 * 105
s
consist of printable ASCII characters.
Solution
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[l]
or s[r]
is a vowel. If both of them are vowels, then we swap the two characters. If not, we will update l
or r
towards the middle by shifting 1 index.
Notice that in the following implementation, we first update l
until 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).
Implementation
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)
How many ways can you arrange the three letters A, B and C?
Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?
Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.