Skip to main content

Longest Sub{string,array}

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

while shrink

1004. Max Consecutive Ones III​

1004. Max Consecutive Ones III

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

487. Max Consecutive Ones II

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

485. Max Consecutive Ones

Easy2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

Easy2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

2024. Maximize the Confusion of an Exam

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

Medium3 solutionsexplanationanalysis3 playgrounds
Solutions:

Explanation

Analysis

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

Hashmap - Unique Elements​

while shrink

3. Longest Substring Without Repeating Characters​

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

1695. Maximum Erasure Value

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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

159. Longest Substring with At Most Two Distinct Characters​

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

904. Fruit Into Baskets

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

1446. Consecutive Characters

Easy2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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)

Depends on prev​

674. Longest Continuous Increasing Subsequence​

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

978. Longest Turbulent Subarray

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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

Bitwise​

2401. Longest Nice Subarray​

2401. Longest Nice Subarray

Medium2 solutionsexplanationanalysis2 playgrounds
Solutions:

Explanation

Analysis

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