Minimum Swaps to Group All 1's Together

Easy

LeetCode ↗

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

1 <= s.length <= 105
s consists of lowercase English letters.

Explain

Explanation

Use two pointers, one at each end of the string. Move both pointers inward while s[left] == s[right].

The only interesting case is the first mismatch. If s[left] != s[right], we are allowed one deletion, so there are only two valid choices: delete s[left] or delete s[right]. That means we only need to check: s[left + 1 : right + 1] and s[left : right]. If either substring is a palindrome, the answer is true; otherwise it is false.

We stop at the first mismatch because any valid solution can use at most one deletion. If we skipped this mismatch and kept scanning, we would be pretending we can delete more than one character.

This runs in O(n) time. The main scan is linear, and at most one mismatch triggers up to two palindrome checks on the remaining substring. Space is O(1) if the palindrome helper uses pointers without creating new strings.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-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

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know

Minimum Swaps to Group All 1's Together

Explanation

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Recommended Readings