Powered by:NEFU AB-IN

Link

2516. 每种字符至少取 K 个

题意

给你一个由字符 ‘a’、‘b’、‘c’ 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

思路

逆向思考：与其思考要取走哪些字符，不如考虑可以保留的最长子串，使得该子串中每种字符的数量不超过 total_counts[char] - k。这样，从两端取走的字符将确保我们至少取走了每种字符的 k 个。
使用滑动窗口技术：在字符串 s 上使用滑动窗口，寻找满足条件的最长子串。我们在窗口内维护每个字符的计数，并根据计数调整窗口大小。

代码

'''
Author: NEFU AB-IN
Date: 2024-09-27 19:41:44
FilePath: \LeetCode\2516\2516.py
LastEditTime: 2024-09-27 19:41:54
'''
# 3.8.9 import
import bisect
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        n = len(s)
        total_counts = Counter(s)
        # 检查每个字符是否至少出现了 k 次
        if any(total_counts[char] < k for char in 'abc'):
            return -1

        # 计算在保留的子串中，每个字符的最大允许次数
        required = {char: total_counts[char] - k for char in 'abc'}

        max_length = 0
        counts = {'a': 0, 'b': 0, 'c': 0}
        left = 0

        # 使用滑动窗口遍历字符串
        for right in range(n):
            counts[s[right]] += 1

            # 如果窗口内某个字符的计数超过了允许的最大次数，收缩窗口
            while any(counts[char] > required[char] for char in 'abc') and left <= right:
                counts[s[left]] -= 1
                left += 1

            current_window_length = right - left + 1
            max_length = Math.max(max_length, current_window_length)

        # 返回需要取走的最少字符数
        return n - max_length