Longest Sub{string,array}
Longest Consecutive x with k impurities (1-pass)
while shrink
1004. Max Consecutive Ones III
Medium·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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
Miscellaneous
1208. Get Equal Substrings Within Budget
Medium·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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
1156. Swap For Longest Repeated Character Substring
Medium·
Solutions:
Visualize
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·
Solutions:
Visualize
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