3223. Minimum Length of String After Operations

Problem

You are given a string s.

You can perform the following process on s any number of times:

• Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].
• Delete the closest character to the left of index i that is equal to s[i].
• Delete the closest character to the right of index i that is equal to s[i].

Return the minimum length of the final string s that you can achieve.

https://leetcode.com/problems/minimum-length-of-string-after-operations/

Example 1:

Input: s = "abaacbcbb"
Output: 5
Explanation:
We do the following operations:

• Choose index 2, then remove the characters at indices 0 and 3. The resulting string is s = "bacbcbb".
• Choose index 3, then remove the characters at indices 0 and 5. The resulting string is s = "acbcb".

Example 2:

Input: s = "aa"
Output: 2
Explanation:
We cannot perform any operations, so we return the length of the original string.

Constraints:

• 1 <= s.length <= 2 * 10⁵
• s consists only of lowercase English letters.

Test Cases

1
2

class Solution:
    def minimumLength(self, s: str) -> int:

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
    ("abaacbcbb", 5),
    ("aa", 2),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, expected):
    assert sol.minimumLength(s) == expected

Thoughts

如果一个字符的个数是奇数，那么操作若干次之后会剩下一个；如果是偶数，会剩下两个。统计每个字符的奇偶性，然后累加。

Code

1
2
3
4
5
6
7
8
9
10

from collections import defaultdict


class Solution:
    def minimumLength(self, s: str) -> int:
        counts = defaultdict(lambda: 2)
        for c in s:
            counts[c] = 3 - counts[c]

        return sum(k for k in counts.values())

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章