Skip to content

Sliding Window Variable Max Advanced

Table of Contents

2730. Find the Longest Semi-Repetitive Substring

2779. Maximum Beauty of an Array After Applying Operation

1838. Frequency of the Most Frequent Element

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, greedy, sliding window, sorting, prefix sum

2516. Take K of Each Character From Left and Right

2831. Find the Longest Equal Subarray

2271. Maximum White Tiles Covered by a Carpet

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, greedy, sliding window, sorting, prefix sum

2106. Maximum Fruits Harvested After at Most K Steps

2555. Maximize Win From Two Segments

2555. Maximize Win From Two Segments - Python Solution
from typing import List


# Sliding Window - Variable
def maximizeWin(prizePositions: List[int], k: int) -> int:
    n = len(prizePositions)

    if 2 * k >= prizePositions[-1] - prizePositions[0]:
        return n

    ans = left = 0
    mx = [0] * (n + 1)

    for right, p in enumerate(prizePositions):
        while p - prizePositions[left] > k:
            left += 1
        ans = max(ans, mx[left] + right - left + 1)
        mx[right + 1] = max(mx[right], right - left + 1)

    return ans


prizePositions = [1, 1, 2, 2, 3, 3, 5]
k = 2
print(maximizeWin(prizePositions, k))  # 7

2009. Minimum Number of Operations to Make Array Continuous

1610. Maximum Number of Visible Points

2781. Length of the Longest Valid Substring

3411. Maximum Subarray With Equal Products

2968. Apply Operations to Maximize Frequency Score

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, sliding window, sorting, prefix sum

1040. Moving Stones Until Consecutive II

3413. Maximum Coins From K Consecutive Bags

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, greedy, sliding window, sorting, prefix sum

395. Longest Substring with At Least K Repeating Characters

1763. Longest Nice Substring

  • LeetCode | LeetCode CH (Easy)

  • Tags: hash table, string, divide and conquer, bit manipulation, sliding window

487. Max Consecutive Ones II

159. Longest Substring with At Most Two Distinct Characters

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, string, sliding window

  • Prerequisite: 3. Longest Substring Without Repeating Characters
159. Longest Substring with At Most Two Distinct Characters - Python Solution
from collections import defaultdict


# Sliding Window - Variable
def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    n = len(s)
    if n <= 2:
        return n

    window = defaultdict(int)
    left, res = 0, 0

    for right in range(n):
        window[s[right]] += 1

        while len(window) > 2:
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1

        res = max(res, right - left + 1)

    return res


s = "ccaabbb"
assert lengthOfLongestSubstringTwoDistinct(s) == 5

340. Longest Substring with At Most K Distinct Characters

340. Longest Substring with At Most K Distinct Characters - Python Solution
from collections import defaultdict


# Sliding Window Variable
def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    n = len(s)
    if n <= k:
        return n

    window = defaultdict(int)
    left, res = 0, 0

    for right in range(n):
        window[s[right]] += 1
        while len(window) > k:
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
        res = max(res, right - left + 1)

    return res


s = "eceba"
k = 2
assert lengthOfLongestSubstringKDistinct(s, k) == 3

Comments