Skip to main content

Longest Sub{string,array}

Longest Consecutive x with k impurities (1-pass)​

while shrink

1004. Max Consecutive Ones III​

Medium·
2 Approachesclick to switch
Explanation

The challenge is to find the maximum number of consecutive 1's in the array nums after flipping at most k zeros to 1's. This is solved using a variable-size sliding window that dynamically adjusts to include as many 1's as possible while allowing up to k zeros within the window.

Expansion:

  • Increment the right pointer to expand the window, increasing the zeros counter if the current element is a zero.

Shrinking:

  • If the zeros count exceeds k, increment the left pointer to shrink the window from the left, decrementing the zeros counter if a zero leaves the window.

Logic:

  • After each adjustment, calculate the current window's length (right - left). Update maxi to keep track of the maximum length found.
Analysis
Time
O(N)
  • The algorithm iterates through each element of nums once, with each element being considered for inclusion in the window exactly once.
Space
O(1)
  • Constant extra space is utilized, with variables to track the window boundaries (left and right), the count of zeros within the window (zeros), and the maximum window length found (maxi).
FIG. 1004 MAX CONSECUTIVE ONES III● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestAllowed(self, arr, allowed, k):
n = len(arr)
left = right = 0
count = maxi = 0
 
isNotAllowed = lambda i: arr[i] != allowed
 
while right < n:
# Expansion
count += isNotAllowed(right)
right += 1
# Shrinking
while left < right and count > k:
count -= isNotAllowed(left)
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def longestOnes(self, nums: List[int], k: int) -> int:
return self.longestAllowed(nums, 1, k)

487. Max Consecutive Ones II​

Medium·
2 Approachesclick to switch
Explanation

This problem extends "Max Consecutive Ones" by allowing for at most one zero to be flipped to one. It can be directly solved by applying the generic longestAllowed approach with allowed = 1 and k = 1.

Analysis
Time
O(N)
  • A single pass through the array with efficient sliding window adjustments.
Space
O(1)
  • Constant extra space is utilized.
FIG. 487 MAX CONSECUTIVE ONES II● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestAllowed(self, arr, allowed, k):
n = len(arr)
left = right = 0
count = maxi = 0
 
isNotAllowed = lambda i: arr[i] != allowed
 
while right < n:
# Expansion
count += isNotAllowed(right)
right += 1
# Shrinking
while left < right and count > k:
count -= isNotAllowed(left)
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
return self.longestAllowed(nums, 1, 1)

485. Max Consecutive Ones​

Easy·
2 Approachesclick to switch
Explanation

The problem seeks to identify the longest sequence of consecutive 1's in the given binary array nums. This is the simplest case where no impurities (0's) are permitted in the sequence (k = 0).

Analysis
Time
O(N)
  • A single traversal through the array.
Space
O(1)
  • Constant space for a fixed number of variables.
FIG. 485 MAX CONSECUTIVE ONES● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestAllowed(self, arr, allowed, k):
n = len(arr)
left = right = 0
count = maxi = 0
 
isNotAllowed = lambda i: arr[i] != allowed
 
while right < n:
# Expansion
count += isNotAllowed(right)
right += 1
# Shrinking
while left < right and count > k:
count -= isNotAllowed(left)
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
return self.longestAllowed(nums, 1, 0)

1493. Longest Subarray of 1's After Deleting One Element​

Medium·
2 Approachesclick to switch
Explanation

This problem seeks the longest subarray of 1's achievable by removing exactly one element from a binary array nums. The window allows at most one zero (k = 1). The length of the subarray after deletion equates to right - left - 1, accounting for the removal of one element.

If nums consists entirely of 1's, removing one element (a 1) results in a subarray one element shorter than the original array (n - 1).

Analysis
Time
O(N)
  • A single traversal through nums.
Space
O(1)
  • Constant space.
FIG. 1493 LONGEST SUBARRAY OF 1S AFTER DELETING ONE ELEMENT● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestAllowed(self, arr, allowed, k):
n = len(arr)
left = right = 0
count = maxi = 0
 
isNotAllowed = lambda i: arr[i] != allowed
 
while right < n:
# Expansion
count += isNotAllowed(right)
right += 1
# Shrinking
while left < right and count > k:
count -= isNotAllowed(left)
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def longestSubarray(self, nums: List[int]) -> int:
return self.longestAllowed(nums, 1, 1) - 1

Longest Consecutive x with k impurities (>1-pass)​

while shrink

1869. Longer Contiguous Segments of Ones than Zeros​

Easy·
2 Approachesclick to switch
Explanation

Determine if the longest contiguous segment of 1's is longer than the longest contiguous segment of 0's. Solved by finding the longest consecutive sequence of each value with k = 0, then comparing.

Analysis
Time
O(2n)
  • n = len(s). checkZeroOnes calls longestAllowed twice, once for "0" and once for "1"; each call's left/right two-pointer scan visits every index once - two separate O(n) passes over s, giving 2n.
Space
O(1)
  • Only scalar counters (left, right, count, maxi) are tracked; nothing scales with n.
FIG. 1869 LONGER CONTIGUOUS SEGMENTS OF ONES THAN ZEROS● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestAllowed(self, arr, allowed, k):
n = len(arr)
left = right = 0
count = maxi = 0
 
isNotAllowed = lambda i: arr[i] != allowed
 
while right < n:
# Expansion
count += isNotAllowed(right)
right += 1
# Shrinking
while left < right and count > k:
count -= isNotAllowed(left)
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def checkZeroOnes(self, s: str) -> bool:
zeros = self.longestAllowed(s, "0", 0)
ones = self.longestAllowed(s, "1", 0)
return ones > zeros

2024. Maximize the Confusion of an Exam​

Medium·
2 Approachesclick to switch
Explanation

Find the maximum number of consecutive same answers achievable by flipping at most k answers. Run longestAllowed once targeting 'T' and once targeting 'F', then take the maximum.

Analysis
Time
O(2N)
  • longestAllowed is a linear two-pointer sweep, O(N), run once targeting 'T' and once targeting 'F' - two separate O(N) passes over answerKey.
Space
O(1)
  • Only scalars (count, maxi, left, right) are tracked; no structure grows with N.
FIG. 2024 MAXIMIZE THE CONFUSION OF AN EXAM● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestAllowed(self, arr, allowed, k):
n = len(arr)
left = right = 0
count = maxi = 0
 
isNotAllowed = lambda i: arr[i] != allowed
 
while right < n:
# Expansion
count += isNotAllowed(right)
right += 1
# Shrinking
while left < right and count > k:
count -= isNotAllowed(left)
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
trues = self.longestAllowed(answerKey, "T", k)
falses = self.longestAllowed(answerKey, "F", k)
return max(trues, falses)

424. Longest Repeating Character Replacement​

Medium·
3 Approachesclick to switch
Explanation

This one-pass solution uses a sliding window and a counter to track character frequencies within the window. The number of replacements needed equals window_length - max_frequency. The window shrinks whenever this exceeds k.

Analysis
Time
O(26N)
  • characterReplacement calls longestAllowed once per uppercase letter, and each call runs its own O(N) sliding window over the string - 26 passes total.
Space
O(1)
  • Only count, maxi, and the pointers are tracked - no structure grows with N.
FIG. 424 LONGEST REPEATING CHARACTER REPLACEMENT● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestAllowed(self, arr, allowed, k):
n = len(arr)
left = right = 0
count = maxi = 0
 
isNotAllowed = lambda i: arr[i] != allowed
 
while right < n:
# Expansion
count += isNotAllowed(right)
right += 1
# Shrinking
while left < right and count > k:
count -= isNotAllowed(left)
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def characterReplacement(self, s: str, k: int) -> int:
maxi = 0
for i in range(ord("A"), ord("Z") + 1):
maxi = max(maxi, self.longestAllowed(s, chr(i), k))
return maxi

2831. Find the Longest Equal Subarray​

Medium·
2 Approachesclick to switch
Explanation

After deleting at most k elements, the longest equal subarray is the longest window whose impurity (elements that are not the most frequent value) is at most k. A counter tracks frequencies in the window and max_freq is the count of the dominant value. The impurity equals window_length - max_freq; whenever it exceeds k, the window shrinks. The answer is the largest max_freq seen.

Analysis
Time
O(N)
  • Each element is added and removed from the window at most once.
Space
O(N)
  • The counter holds at most one entry per distinct value.
FIG. 2831 FIND THE LONGEST EQUAL SUBARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestEqualSubarray(self, nums: List[int], k: int) -> int:
n = len(nums)
left = right = 0
maxi = 0
counter = collections.Counter()
max_freq = 0
 
getImpurityCount = lambda: right - left - max_freq
 
while right < n:
# Expansion
counter[nums[right]] += 1
max_freq = max(max_freq, counter[nums[right]])
right += 1
# Shrinking
while left < right and getImpurityCount() > k:
counter[nums[left]] -= 1
left += 1
# Logic
maxi = max(maxi, max_freq)
return maxi

Hashmap - Unique Elements​

while shrink

3. Longest Substring Without Repeating Characters​

2 Approachesclick to switch
Explanation

Find the length of the longest substring without any repeating characters. A sliding window with a counter tracks character frequencies. The window shrinks whenever a duplicate is detected (when the number of unique keys in the counter is less than the window length).

Analysis
Time
O(n)
  • Single pass through the string of length n, with each character considered exactly once.
Space
O(26)
  • The counter tracks character frequencies; at worst case, s can contain all lowercase alphabets.
FIG. 3 LONGEST SUBSTRING WITHOUT REPEATING CHARACTERS● INTERACTIVE
visualization loads as you reach it
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
left = right = 0
counter = collections.Counter()
maxi = 0
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter[s[right - 1]] > 1:
counter[s[left]] -= 1
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi

1695. Maximum Erasure Value​

Medium·
Explanation

Can be restated as "Find the maximum sum of subarray with unique elements". A sliding window with a counter tracks element uniqueness while maintaining a running total. The window shrinks whenever a duplicate is found.

Analysis
Time
O(n)
  • Single pass through nums (length n); left and right each advance at most n steps.
Space
O(n)
  • counter can hold up to n unique elements.
FIG. 1695 MAXIMUM ERASURE VALUE● INTERACTIVE
visualization loads as you reach it
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
n = len(nums)
left = right = 0
counter = collections.Counter()
maxi = total = 0
while right < n:
# Expansion
counter[nums[right]] += 1
total += nums[right]
right += 1
# Shrinking
while left < right and counter[nums[right - 1]] > 1:
counter[nums[left]] -= 1
total -= nums[left]
left += 1
# Logic
maxi = max(maxi, total)
return maxi

Hashmap - K Distinct Elements​

while shrink

340. Longest Substring with At Most K Distinct Characters​

Medium·
2 Approachesclick to switch
Explanation

Find the length of the longest substring that contains at most k distinct characters. A sliding window with a counter tracks character frequencies. The window shrinks whenever the distinct character count exceeds k.

Analysis
Time
O(N)
  • Single pass through the string with constant-time adjustments.
Space
O(k)
  • The counter holds at most k distinct characters.
FIG. 340 LONGEST SUBSTRING WITH AT MOST K DISTINCT CHARACTERS● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
n = len(s)
left = right = 0
counter = Counter()
maxi = 0
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[s[left]] -= 1
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi

Longest Substring with K Uniques​

Medium·
Explanation

Find the length of the longest substring that contains exactly k distinct characters. A sliding window with a counter tracks character frequencies and shrinks whenever the distinct count exceeds k. The answer is only recorded when the window holds exactly k distinct characters, and stays -1 if no such substring exists.

Analysis
Time
O(N)
  • Single pass through the string; left and right each move at most N steps.
Space
O(k)
  • The counter holds at most k distinct characters.
FIG. LONGEST K UNIQUE● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def longestKSubstr(self, s, k):
n = len(s)
left = right = 0
counter = Counter()
maxi = -1
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[s[left]] -= 1
left += 1
# Logic
if counter.distinct_count() == k:
maxi = max(maxi, right - left)
return maxi

159. Longest Substring with At Most Two Distinct Characters​

Medium·
2 Approachesclick to switch
Explanation

A specific instance of "Longest Substring with At Most K Distinct Characters" where k = 2.

Analysis
Time
O(N)
  • Single pass through the string.
Space
O(1)
  • The counter is limited to at most k = 2 distinct characters, a fixed constant regardless of N.
FIG. 159 LONGEST SUBSTRING WITH AT MOST TWO DISTINCT CHARACTERS● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
n = len(s)
left = right = 0
counter = Counter()
maxi = 0
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[s[left]] -= 1
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
return self.lengthOfLongestSubstringKDistinct(s, 2)

904. Fruit Into Baskets​

Medium·
2 Approachesclick to switch
Explanation

A special case of "Longest Substring with At Most K Distinct Characters" where k = 2, but with an array of integers instead of a string.

Analysis
Time
O(n)
  • Single pass through the array.
Space
O(1)
  • The basket counter holds at most k = 2 distinct fruit types, a fixed bound independent of n.
FIG. 904 FRUIT INTO BASKETS● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
n = len(s)
left = right = 0
counter = Counter()
maxi = 0
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[s[left]] -= 1
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def totalFruit(self, fruits: List[int]) -> int:
return self.lengthOfLongestSubstringKDistinct(fruits, 2)

1446. Consecutive Characters​

Easy·
2 Approachesclick to switch
Explanation

Find the maximum power of a string, defined as the maximum length of a non-empty substring that contains only one unique character. This is "Longest Substring with At Most K Distinct Characters" where k = 1.

Analysis
Time
O(N)
  • Single traversal through the string.
Space
O(1)
  • Constant space.
FIG. 1446 CONSECUTIVE CHARACTERS● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
n = len(s)
left = right = 0
counter = Counter()
maxi = 0
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[s[left]] -= 1
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi
 
def maxPower(self, s: str) -> int:
return self.lengthOfLongestSubstringKDistinct(s, 1)

395. Longest Substring with At Least K Repeating Characters​

Medium·
Explanation

The "at least k" constraint is not monotonic, so a single window cannot slide directly. Instead, fix the number of distinct characters allowed (maxUnique, from 1 up to the total distinct count) and, for each value, find the longest window holding at most that many distinct characters. A window is the answer when every distinct character in it appears at least k times - detected by comparing uniqueChars against countAtLeastK.

Analysis
Time
O(N + N * M)
  • maxUniqueChars = len(set(s)) is one O(N) pass over s.
  • M is the number of distinct characters in s (at most 26). The outer for loop calls atMostKUniqueChars once per value from 1 to M, and each call is an O(N) two-pointer scan - N * M.
Space
O(1)
  • counter and the set(s) used to compute maxUniqueChars hold at most 26 distinct characters.
FIG. 395 LONGEST SUBSTRING WITH AT LEAST K REPEATING CHARACTERS● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
def atMostKUniqueChars(maxUnique):
n = len(s)
left = right = 0
counter = collections.Counter()
uniqueChars = 0 # Number of unique characters in the current window
countAtLeastK = 0 # Number of characters that appear at least k times in the current window
longest = 0
 
while right < n:
# Expansion
if counter[s[right]] == 0:
uniqueChars += 1
counter[s[right]] += 1
if counter[s[right]] == k:
countAtLeastK += 1
right += 1
 
# Shrinking
while left < right and uniqueChars > maxUnique:
if counter[s[left]] == k:
countAtLeastK -= 1
counter[s[left]] -= 1
if counter[s[left]] == 0:
uniqueChars -= 1
left += 1
 
# Logic
if uniqueChars == countAtLeastK:
longest = max(longest, right - left)
 
return longest
 
maxUniqueChars = len(set(s)) # Maximum possible unique characters in s
maxi = 0
for maxUnique in range(1, maxUniqueChars + 1):
maxi = max(maxi, atMostKUniqueChars(maxUnique))
 
return maxi

Depends on prev​

674. Longest Continuous Increasing Subsequence​

Easy·
Explanation

Find the length of the longest continuous increasing subsequence (LCIS). The window expands as long as each element is greater than the previous one. When the increasing sequence breaks, the window rapidly shrinks to start from the current position.

Expansion:

  • The window expands by moving the right pointer forward as long as the current element is greater than the previous one.

Logic:

  • After each expansion, update maxi with the current window length.

Shrinking:

  • When the increasing sequence breaks, set left to right and restart.
Analysis
Time
O(N)
  • Single pass through the array.
Space
O(1)
  • Constant space for a few variables.
FIG. 674 LONGEST CONTINUOUS INCREASING SUBSEQUENCE● INTERACTIVE
visualization loads as you reach it
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
n = len(nums)
left = right = 0
maxi = 0
 
isStrictlyIncreasing = lambda i: nums[i - 1] > nums[i - 2]
while right < n:
# Expansion
right += 1
# Shrinking
while left < right - 1 and not isStrictlyIncreasing(right):
left += 1
# Logic
maxi = max(maxi, right - left)
return maxi

1839. Longest Substring Of All Vowels in Order​

Medium·
Explanation

Find the length of the longest "beautiful" substring that contains all five vowels ('a', 'e', 'i', 'o', 'u') in order. The window expands as long as characters remain in non-decreasing order. A seen set tracks which vowels have been encountered. When the order breaks, the window resets.

Analysis
Time
O(n)
  • n is the length of word - left and right each advance at most n times across the run, so every character is visited once.
Space
O(1)
  • counter only ever tracks the 5 vowels, a fixed-size bound independent of n.
FIG. 1839 LONGEST SUBSTRING OF ALL VOWELS IN ORDER● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def longestBeautifulSubstring(self, word: str) -> int:
n = len(word)
left = right = 0
maxi = 0
counter = Counter()
 
isStrictlyIncreasing = lambda i: word[i - 1] >= word[i - 2]
 
while right < n:
# Expansion
counter[word[right]] += 1
right += 1
# Shrinking
while left < right - 1 and not isStrictlyIncreasing(right):
counter[word[left]] -= 1
left += 1
# Logic
if counter.distinct_count() == 5:
maxi = max(maxi, right - left)
return maxi

978. Longest Turbulent Subarray​

Medium·
Explanation

A turbulent subarray alternates between elements being strictly greater and then less than (or vice versa) adjacent elements. The window expands as long as the turbulent pattern holds. When the pattern breaks, the window rapidly shrinks.

Tracking the comparison sign between adjacent elements gives the running turbulent subarray count

Analysis
Time
O(N)
  • Single pass through the array with each element evaluated once.
Space
O(1)
  • A minimal number of variables.
FIG. 978 LONGEST TURBULENT SUBARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
def isTurbulent(l: int, r: int) -> bool:
# 1. A window of size 1 (or 0) is always valid
if r - l <= 1:
return True
 
# 2. Rule breaks if the newest two elements are flat
if arr[r - 1] == arr[r - 2]:
return False
 
# 3. Rule breaks if the newest three elements (within our window) move same direction
if r - l >= 3 and (arr[r - 1] > arr[r - 2]) == (arr[r - 2] > arr[r - 3]):
return False
 
return True
 
n = len(arr)
if n < 2:
return n
 
left = right = 0
maxi = 1
 
while right < n:
# Expansion
right += 1
# Shrinking
while left < right and not isTurbulent(left, right):
left += 1
# Logic
maxi = max(maxi, right - left)
 
return maxi

2419. Longest Subarray With Maximum Bitwise AND​

Medium·
2 Approachesclick to switch
Explanation

ANDing two numbers can only clear bits, never set them, so the AND of any subarray is at most max(subarray) - and it equals that max only when every element in the subarray already equals the array's overall maximum. The problem reduces to: find the longest run of consecutive elements equal to max(nums).

Compute max_element once, then make a single pass counting the current run (consec), resetting to 0 on any mismatch and tracking the best run seen (maxi).

Analysis
Time
O(2N)
  • One O(N) pass to find max(nums), then a second O(N) pass to count the longest run - 2N.
Space
O(1)
  • A few counters, no extra structures.
FIG. 2419 LONGEST SUBARRAY WITH MAXIMUM BITWISE AND TWO PASS● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
max_element = max(nums)
consec = maxi = 0
for i in range(len(nums)):
if nums[i] == max_element:
consec += 1
else:
consec = 0
maxi = max(maxi, consec)
return maxi

Miscellaneous​

1208. Get Equal Substrings Within Budget​

Medium·
2 Approachesclick to switch
Explanation

Find the maximum length of a substring of s that can be made equal to the corresponding substring of t, where the total cost does not exceed maxCost. The cost is the absolute difference in ASCII values between corresponding characters. The window expands by accumulating costs and shrinks when the budget is exceeded.

Analysis
Time
O(N)
  • right advances across all n = len(s) positions exactly once, and left never moves past right, so the inner while shrink loop can advance left at most n times total across the whole run.
Space
O(1)
  • Only left, right, maxi, and cost are tracked; no structure scales with n.
FIG. 1208 GET EQUAL SUBSTRINGS WITHIN BUDGET● INTERACTIVE
visualization loads as you reach it
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
n = len(s)
left = right = 0
maxi = cost = 0
getCost = lambda i: abs(ord(s[i]) - ord(t[i]))
while right < n:
cost += getCost(right)
right += 1
while left < right and cost > maxCost:
cost -= getCost(left)
left += 1
maxi = max(maxi, right - left)
return maxi

1658. Minimum Operations to Reduce X to Zero​

Medium·
Explanation

To find the shortest operations that sum up to x from both ends is to find the longest subarray that sums up to total - x.

Instead of directly finding elements to remove from both ends, identify the largest contiguous subarray with sum equal to sum(nums) - x. The answer is n - length_of_that_subarray.

Finding the shortest ends summing to x is the same as finding the longest middle summing to total - x

Analysis
Time
O(2N)
  • k = sum(nums) - x is one O(N) pass, then the sliding window makes a second O(N) pass, adding and removing each element exactly once - two distinct O(N) passes, 2N.
Space
O(1)
  • Only a fixed number of variables are used regardless of N.
FIG. 1658 MINIMUM OPERATIONS TO REDUCE X TO ZERO● INTERACTIVE
visualization loads as you reach it
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
n = len(nums)
left = right = 0
maxi, total = -1, 0
k = sum(nums) - x
while right < n:
# Expansion
total += nums[right]
right += 1
# Shrinking
while left < right and total > k:
total -= nums[left]
left += 1
# Logic
if total == k:
maxi = max(maxi, right - left)
return len(nums) - maxi if maxi != -1 else -1

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit​

Medium·
3 Approachesclick to switch
Explanation

The window is valid only while max(window) - min(window) <= limit. To check that in a sliding window we keep two heaps over (value, index) pairs: a min-heap for the window minimum and a max-heap for the window maximum.

Expansion:

  • Push nums[right] into both heaps and advance right.

Shrinking:

  • While the window is invalid (abs(min_heap[0][0] - max_heap[0][0]) > limit), advance left, lazily popping any heap tops whose stored index has fallen out of the window (index <= left).

Logic:

  • After each adjustment, update maxi with the current window length right - left.

Indices are stored alongside values so stale extremes can be discarded lazily - a heap entry is only removed once left passes its index, so each element is pushed and popped at most once.

Analysis
Time
O(N log N)
  • Each element is pushed and popped from each heap at most once; every heap operation is O(log N).
Space
O(N)
  • In the worst case both heaps hold all N elements.
FIG. 1438 LONGEST CONTINUOUS SUBARRAY WITH ABSOLUTE DIFF LESS THAN OR EQUAL TO LIMIT● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
n = len(nums)
left = right = 0
maxi = 0
min_heap = []
max_heap = []
isValid = lambda: abs(min_heap[0][0] - max_heap[0][0]) <= limit
while right < n:
heapq.heappush(min_heap, (nums[right], right))
heapq.heappush_max(max_heap, (nums[right], right))
right += 1
while left < right and not isValid():
while min_heap[0][1] <= left:
heapq.heappop(min_heap)
while max_heap[0][1] <= left:
heapq.heappop_max(max_heap)
left += 1
maxi = max(maxi, right - left)
return maxi

2779. Maximum Beauty of an Array After Applying Operation​

Medium·
Explanation

Two elements can be turned into the same value exactly when their [i-k, i+k] ranges overlap, which is when they differ by at most 2*k. Sorting nums turns that into a locality property: a group can all become one value iff its smallest and largest differ by at most 2*k, and the extremes of any group are its first and last element once sorted. So slide a window over the sorted array - grow right, then shrink left while nums[right-1] - nums[left] > 2*k. Every window that survives the shrink is a valid group, so maxi just tracks the widest one.

Analysis
Time
O(2n + n log n)
  • nums.sort() is O(n log n).
  • right advances n times and left advances at most n times across the whole run - neither pointer ever moves backwards - so the two-pointer scan is 2n.
Space
O(sort)
  • Only the scalars n, left, right, maxi are allocated, so the sort's own working memory is the entire cost.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 2779 MAXIMUM BEAUTY SLIDING WINDOW● INTERACTIVE
visualization loads as you reach it
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
left = right = 0
maxi = 0
while right < n:
right += 1
while left < right and nums[right - 1] - nums[left] > 2 * k:
left += 1
maxi = max(maxi, right - left)
return maxi

1156. Swap For Longest Repeated Character Substring​

Medium·
Explanation

A single swap can extend a run of one character. Slide a window that stays valid while it contains at most one character different from the rest ((right - left) - max_frequency <= 1). The candidate length is capped by min(window_size, total_count_of_that_char) - you can only swap in another copy of the character if one exists somewhere else in the string.

Analysis
Time
O(N)
  • Single pass with the sliding window; left and right each advance at most N times.
Space
O(1)
  • The frequency maps hold at most 26 distinct characters.
FIG. 1156 SWAP FOR LONGEST REPEATED CHARACTER SUBSTRING● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxRepOpt1(self, text: str) -> int:
counter = collections.Counter(text)
left = right = 0
n = len(text)
maxi = 0
freqCounter = collections.defaultdict(int)
 
# Iterate through the string with a sliding window
while right < n:
# Expand the window
freqCounter[text[right]] += 1
right += 1
 
# Check if window is valid - contains more than one type of character more than once
while (right - left) - max(freqCounter.values()) > 1:
# Shrink the window from the left
freqCounter[text[left]] -= 1
left += 1
 
# Update maxi to the max length of the window considering all instances of the character in text
# It considers swapping one character if it increases the window size and if another instance of the character exists outside the current window
maxi = max(maxi, min((right - left), counter[text[right - 1]]))
 
return maxi

Bitwise​

2401. Longest Nice Subarray​

Medium·
2 Approachesclick to switch
Explanation

A subarray is "nice" if the bitwise AND of every pair of elements equals 0 (no two elements share a set bit). The key insight: if all elements in a window have no overlapping bits, their sum equals their XOR (XOR = addition without carries; any carry means a bit collision). The window shrinks from the left whenever sum ≠ XOR. Both operations are losslessly reversible: shrinking subtracts the left element and XORs it out.

Analysis
Time
O(n)
  • right advances through nums once in the outer while right < n loop, and left (in the inner shrink loop) only ever moves forward, so each index enters and leaves the window at most once: O(n), where n is len(nums).
Space
O(1)
  • Only scalars (left, right, maxi, window_sum, window_xor) are tracked, no structure grows with n.
FIG. 2401 LONGEST NICE SUBARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestNiceSubarray(self, nums: List[int]) -> int:
n = len(nums)
left = right = 0
maxi = 0
 
# Track both lossless states
window_sum = 0
window_xor = 0
 
while right < n:
# 1. Expansion
# Both addition and XOR are perfectly reversible!
window_sum += nums[right]
window_xor ^= nums[right]
right += 1
 
# 2. Shrinking
# If the Sum and XOR don't match, bits collided and caused a carry.
# Pull left forward and reverse the operations until they match again.
while left < right and window_sum != window_xor:
window_sum -= nums[left]
window_xor ^= nums[left]
left += 1
 
# 3. Logic
maxi = max(maxi, right - left)
 
return maxi