Skip to main content

Longest Sub{string,array}

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

while shrink

1004. Max Consecutive Ones III​

Medium·
Solutions:
FIG. 1004 MAX CONSECUTIVE ONES III● INTERACTIVE
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:
FIG. 487 MAX CONSECUTIVE ONES II● INTERACTIVE
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:
FIG. 485 MAX CONSECUTIVE ONES● INTERACTIVE
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:
FIG. 1493 LONGEST SUBARRAY OF 1S AFTER DELETING ONE ELEMENT● INTERACTIVE
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:
FIG. 1869 LONGER CONTIGUOUS SEGMENTS OF ONES THAN ZEROS● INTERACTIVE
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:
FIG. 2024 MAXIMIZE THE CONFUSION OF AN EXAM● INTERACTIVE
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:
FIG. 424 LONGEST REPEATING CHARACTER REPLACEMENT● INTERACTIVE
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:
FIG. 2831 FIND THE LONGEST EQUAL SUBARRAY● INTERACTIVE
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:
FIG. 3 LONGEST SUBSTRING WITHOUT REPEATING CHARACTERS● INTERACTIVE
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:
FIG. 1695 MAXIMUM ERASURE VALUE● INTERACTIVE
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:
FIG. 340 LONGEST SUBSTRING WITH AT MOST K DISTINCT CHARACTERS● INTERACTIVE
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:
FIG. LONGEST K UNIQUE● INTERACTIVE
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:
FIG. 159 LONGEST SUBSTRING WITH AT MOST TWO DISTINCT CHARACTERS● INTERACTIVE
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:
FIG. 904 FRUIT INTO BASKETS● INTERACTIVE
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:
FIG. 1446 CONSECUTIVE CHARACTERS● INTERACTIVE
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:
FIG. 395 LONGEST SUBSTRING WITH AT LEAST K REPEATING CHARACTERS● INTERACTIVE
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:
FIG. 674 LONGEST CONTINUOUS INCREASING SUBSEQUENCE● INTERACTIVE
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:
FIG. 1839 LONGEST SUBSTRING OF ALL VOWELS IN ORDER● INTERACTIVE
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:
FIG. 978 LONGEST TURBULENT SUBARRAY● INTERACTIVE
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:
FIG. 1208 GET EQUAL SUBSTRINGS WITHIN BUDGET● INTERACTIVE
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:
FIG. 1658 MINIMUM OPERATIONS TO REDUCE X TO ZERO● INTERACTIVE
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:
FIG. 1438 LONGEST CONTINUOUS SUBARRAY WITH ABSOLUTE DIFF LESS THAN OR EQUAL TO LIMIT● INTERACTIVE
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:
FIG. 1156 SWAP FOR LONGEST REPEATED CHARACTER SUBSTRING● INTERACTIVE
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:
FIG. 2401 LONGEST NICE SUBARRAY● INTERACTIVE
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