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)
Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following is a good use case for backtracking?

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Implementation

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?


Recommended Readings


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.


TA 👨‍🏫