Fixed Window
while expand
Naïve Sum/Average
Max Sum Subarray of size K
Easy·
Solutions:
Visualize
class Solution:
def maxSubarraySum(self, arr, k):
n = len(arr)
left = right = 0
total = maxi = 0
while right < n:
# Expansion
while right < n and right - left < k:
total += arr[right]
right += 1
# Logic
maxi = max(maxi, total)
# Shrinking
total -= arr[left]
left += 1
return maxi
643. Maximum Average Subarray I
Easy·
Solutions:
Visualize
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
n = len(nums)
left = right = 0
maxi = -float("inf") # Since negative numbers are allowed in the array
total = 0
while right < n:
# Expansion
while right < n and right - left < k:
total += nums[right]
right += 1
# Logic
maxi = max(maxi, total / k)
# Shrinking
total -= nums[left]
left += 1
return maxi
1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
Medium·
Solutions:
Visualize
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
n = len(arr)
left = right = 0
total = count = 0
isAboveThreshold = lambda total: total / k >= threshold
while right < n:
# Expansion
while right < n and right - left < k:
total += arr[right]
right += 1
# Logic
count += isAboveThreshold(total)
# Shrinking
total -= arr[left]
left += 1
return count
2090. K Radius Subarray Averages
Medium·
Solutions:
Visualize
class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
w = 2 * k + 1 # window size
left = right = 0
result = [-1] * n
total = 0
getCenter = lambda left, right: left + k
getAvg = lambda total: total // w
while right < n:
# Expansion
while right < n and right - left < w:
total += nums[right]
right += 1
# Logic
if right - left == w:
result[getCenter(left, right)] = getAvg(total)
# Shrinking
total -= nums[left]
left += 1
return result
1423. Maximum Points You Can Obtain from Cards
Medium·
Solutions:
Visualize
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
w = n - k # We need to minimize sum of window with size n-k
left = right = 0
total = 0
mini = float("inf")
arr_total = sum(cardPoints)
if k >= n:
return arr_total
while right < n:
# Expansion
while right < n and right - left < w:
total += cardPoints[right]
right += 1
# Logic
mini = min(mini, total)
# Shrinking
total -= cardPoints[left]
left += 1
return arr_total - mini
1176. Diet Plan Performance
Easy·
Solutions:
Visualize
class Solution:
def dietPlanPerformance(
self, calories: List[int], k: int, lower: int, upper: int
) -> int:
n = len(calories)
left = right = 0
total = points = 0
getPerformance = lambda total: (total > upper) - (total < lower)
while right < n:
# Expansion
while right < n and right - left < k:
total += calories[right]
right += 1
# Logic
points += getPerformance(total)
# Shrinking
total -= calories[left]
left += 1
return points
1052. Grumpy Bookstore Owner
Medium·
Solutions:
Visualize
class Solution:
def maxSatisfied(
self, customers: List[int], grumpy: List[int], minutes: int
) -> int:
n = len(customers)
left = right = 0
# Calculate already satisfied customers, ignoring grumpy periods
total = sum(i * (not j) for i, j in zip(customers, grumpy))
maxi = 0
getGrumpyScore = lambda idx: customers[idx] * grumpy[idx]
while right < n:
# Expansion
while right < n and right - left < minutes:
# Expansion: Add customers affected by grumpiness within the window
total += getGrumpyScore(right)
right += 1
# Logic
maxi = max(maxi, total)
# Shrinking
total -= getGrumpyScore(left)
left += 1
return maxi
1652. Defuse the Bomb
Easy·
Solutions:
Visualize
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
left = right = 0
negative, k = k < 0, abs(k)
total = 0
result = [0] * n
getPosition = lambda: right % n if negative else (left - 1) % n
while right < n + k - 1:
# Expansion
while right < n + k - 1 and right - left < k:
total += code[right % n]
right += 1
# Logic
result[getPosition()] = total
# Shrinking
total -= code[left]
left += 1
return result
Hashmap
187. Repeated DNA Sequences
Medium·
Solutions:
Visualize
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
n = len(s)
k = 10
left = right = 0
counter = collections.Counter()
result = []
while right < n:
# Expansion
while right < n and right - left < k:
right += 1
# Logic
substring = s[left:right]
counter[substring] += 1
if counter[substring] == 2:
result.append(substring)
# Shrinking
left += 1
return result
Hashmap - Duplicate Elements
219. Contains Duplicate II
Easy·
Solutions:
Visualize
class Solution:
def containsDuplicatesInK(self, arr: List[int], k: int) -> bool:
n = len(arr)
left = right = 0
counter = collections.Counter()
while right < n:
# Expansion
while right < n and right - left < k:
counter[arr[right]] += 1
# Logic
if counter[arr[right]] > 1:
return True
right += 1
# Shrinking
counter[arr[left]] -= 1
left += 1
return False
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
k = k + 1 # since there is an '=' in abs(i - j) <= k
return self.containsDuplicatesInK(nums, k)
217. Contains Duplicate
Easy·
Solutions:
Visualize
class Solution:
def containsDuplicatesInK(self, arr: List[int], k: int) -> bool:
n = len(arr)
left = right = 0
counter = collections.Counter()
while right < n:
# Expansion
while right < n and right - left < k:
counter[arr[right]] += 1
# Logic
if counter[arr[right]] > 1:
return True
right += 1
# Shrinking
counter[arr[left]] -= 1
left += 1
return False
def containsDuplicate(self, nums: List[int]) -> bool:
k = len(nums) # since entire array is considered
return self.containsDuplicatesInK(nums, k)
Hashmap - Unique/Distinct Elements
1876. Substrings of Size Three with Distinct 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 countGoodSubstrings(self, s: str) -> int:
n = len(s)
k = 3 # Fixed window size for substrings of length three
left = right = 0
counter = Counter()
good_substrings = 0
# Lambda function to check if the window has distinct characters
isGoodSubstring = lambda: counter.distinct_count() == k
while right < n:
# Expansion: Update the character frequency in the window
while right < n and right - left < k:
counter[s[right]] += 1
right += 1
# Logic: If all characters in the window are distinct, increment ans
good_substrings += isGoodSubstring()
# Shrinking: Move the window forward by adjusting character frequencies
counter[s[left]] -= 1
left += 1
return good_substrings
1852. Distinct Numbers in Each Subarray
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 distinctNumbers(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
left = right = 0
result = []
counter = Counter()
while right < n:
# Expansion
while right < n and right - left < k:
counter[nums[right]] += 1
right += 1
# Logic
result.append(counter.distinct_count())
# Shrinking
counter[nums[left]] -= 1
left += 1
return result
2107. Number of Unique Flavors After Sharing K Candies
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 shareCandies(self, candies: List[int], k: int) -> int:
n = len(candies)
left = right = 0
counter = Counter(candies)
maxi = 0
if k == 0:
return counter.distinct_count()
while right < n:
# Expansion
while right < n and right - left < k:
counter[candies[right]] -= 1
right += 1
# Logic
maxi = max(maxi, counter.distinct_count())
# Shrinking
counter[candies[left]] += 1
left += 1
return maxi
1100. Find K-Length Substrings With No Repeated 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 numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
n = len(s)
left = right = 0
counter = Counter()
ans = 0
isDistinct = lambda: counter.distinct_count() == k
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] += 1
right += 1
# Logic
ans += isDistinct()
# Shrinking
counter[s[left]] -= 1
left += 1
return ans
Substrings of length k with k-1 distinct elements
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 substrCount(self, s, k):
n = len(s)
left = right = 0
counter = Counter()
ans = 0
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] += 1
right += 1
# Logic
ans += counter.distinct_count() == k - 1
# Shrinking
counter[s[left]] -= 1
left += 1
return ans
2461. Maximum Sum of Distinct Subarrays With Length K
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 maximumSubarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
left = right = 0
counter = Counter()
maxi = total = 0
# Lambda function to check if the window has distinct characters
isUnique = lambda: counter.distinct_count() == k
while right < n:
# Expansion
while right < n and right - left < k:
counter[nums[right]] += 1
total += nums[right]
right += 1
# Logic
if isUnique():
maxi = max(maxi, total)
# Shrinking
counter[nums[left]] -= 1
total -= nums[left]
left += 1
return maxi
2841. Maximum Sum of Almost Unique Subarray
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 maxSum(self, nums: List[int], m: int, k: int) -> int:
n = len(nums)
left = right = 0
counter = Counter()
maxi = total = 0
# Lambda function to check if the window has distinct characters
isAlmostUnique = lambda: counter.distinct_count() >= m
while right < n:
# Expansion
while right < n and right - left < k:
counter[nums[right]] += 1
total += nums[right]
right += 1
# Logic
if isAlmostUnique():
maxi = max(maxi, total)
# Shrinking
counter[nums[left]] -= 1
total -= nums[left]
left += 1
return maxi
1297. Maximum Number of Occurrences of a Substring
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 maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
n = len(s)
k = minSize
left = right = 0
substrings = collections.defaultdict(int)
maxi = 0
counter = Counter()
while right < n:
while right < n and right - left < k:
counter[s[right]] += 1
right += 1
# print(left, right, counter.distinct_count())
if counter.distinct_count() <= maxLetters:
substrings[s[left:right]] += 1
maxi = max(maxi, substrings[s[left:right]])
counter[s[left]] -= 1
left += 1
return maxi
Hashmap - Anagrams/Permutations
438. Find All Anagrams in a String
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 findAnagrams(self, s: str, p: str) -> List[int]:
n = len(s)
k = len(p)
left = right = 0
counter = Counter(p)
ans = []
isAnagram = lambda: counter.distinct_count() == 0
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] -= 1
right += 1
# Logic
if isAnagram():
ans.append(left)
# Shrinking
counter[s[left]] += 1
left += 1
return ans
242. Valid Anagram
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 findAnagrams(self, s: str, p: str) -> List[int]:
n = len(s)
k = len(p)
left = right = 0
counter = Counter(p)
ans = []
isAnagram = lambda: counter.distinct_count() == 0
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] -= 1
right += 1
# Logic
if isAnagram():
ans.append(left)
# Shrinking
counter[s[left]] += 1
left += 1
return ans
def isAnagram(self, s: str, t: str) -> bool:
return len(s) == len(t) and self.findAnagrams(s, t) == [0]
567. Permutation in String
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 findAnagrams(self, s: str, p: str) -> List[int]:
n = len(s)
k = len(p)
left = right = 0
counter = Counter(p)
ans = []
is_anagram = lambda: counter.distinct_count() == 0
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] -= 1
right += 1
# Logic
if is_anagram():
ans.append(left)
# Shrinking
counter[s[left]] += 1
left += 1
return ans
def checkInclusion(self, s1: str, s2: str) -> bool:
return self.findAnagrams(s2, s1) != []
Count
2379. Minimum Recolors to Get K Consecutive Black Blocks
Easy·
Solutions:
Visualize
class Solution:
def minimumRecolors(self, blocks: str, k: int) -> int:
n = len(blocks)
left = right = 0
mini = n
whites = 0
isWhite = lambda i: blocks[i] == "W"
while right < n:
# Expansion
while right < n and right - left < k:
whites += isWhite(right)
right += 1
# Logic
mini = min(mini, whites)
# Shrinking
whites -= isWhite(left)
left += 1
return mini
1456. Maximum Number of Vowels in a Substring of Given Length
Medium·
Solutions:
Visualize
class Solution:
def maxVowels(self, s: str, k: int) -> int:
n = len(s)
left = right = 0
maxi = count = 0
vowels = set("aeiou")
isVowel = lambda i: s[i] in vowels
while right < n:
# Expansion
while right < n and right - left < k:
count += isVowel(right)
right += 1
# Logic
maxi = max(maxi, count)
# Shrinking
count -= isVowel(left)
left += 1
return maxi
Count - Math
1550. Three Consecutive Odds
Easy·
Solutions:
Visualize
class Solution:
def threeConsecutiveOdds(self, arr: List[int]) -> bool:
n, k = len(arr), 3
left = right = 0
odds = 0
isOdd = lambda i: arr[i] % 2
while right < n:
# Expansion
while right < n and right - left < k:
odds += isOdd(right)
right += 1
# Logic
if odds == k:
return True
# Shrinking
odds -= isOdd(left)
left += 1
return False
2269. Find the K-Beauty of a Number
Easy·
Solutions:
Visualize
class Solution:
def divisorSubstrings(self, num: int, k: int) -> int:
n = int(math.log10(num)) + 1
left = right = 0
ans = sub_num = 0
isDivisible = lambda: int(num) % sub_num == 0 if sub_num != 0 else 0
while right < n:
# Expansion
while right < n and right - left < k:
power = 10 ** (n - right - 1)
digit = (num // power) % 10
sub_num = sub_num * 10 + digit
right += 1
# Logic
ans += isDivisible()
# Shrinking
sub_num = sub_num % (10 ** (k - 1))
left += 1
return ans
Count - Swaps
1151. Minimum Swaps to Group All 1's Together
Medium·
Solutions:
Visualize
class Solution:
def minSwaps(self, data: List[int]) -> int:
n, k = len(data), data.count(1)
left = right = zeroes = 0
mini = n
if k == 0:
return 0
isZero = lambda i: data[i] == 0
while right < n:
# Expansion
while right < n and right - left < k:
zeroes += isZero(right)
right += 1
# Logic
mini = min(mini, zeroes)
# Shrinking
zeroes -= isZero(left)
left += 1
return mini
2134. Minimum Swaps to Group All 1's Together II
Medium·
Solutions:
Visualize
class Solution:
def minSwaps(self, nums: List[int]) -> int:
n = len(nums) * 2 - 1
k = nums.count(1)
left = right = zeroes = 0
mini = n
if k == 0:
return 0
isZero = lambda i: nums[i % len(nums)] == 0
while right < n:
# Expansion
while right < n and right - left < k:
zeroes += isZero(right)
right += 1
# Logic
mini = min(mini, zeroes)
# Shrinking
zeroes -= isZero(left)
left += 1
return mini
Heap
239. Sliding Window Maximum
Solutions:
Visualize
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
left = right = 0
heap = [] # Max heap
result = []
while right < n:
# Expansion: Add new elements to the heap
while right < n and right - left < k:
heapq.heappush_max(heap, (nums[right], right))
right += 1
# Logic: Append the current maximum to ans
result.append(heap[0][0])
left += 1
# Shrinking: Ensure the top of the heap is within the current window
while heap and heap[0][1] < left:
heapq.heappop_max(heap)
return result
Deque
First negative in every window of size k
Medium·
Solutions:
Visualize
import collections
class Solution:
def firstNegInt(self, arr, k):
n = len(arr)
left = right = 0
negatives = collections.deque()
result = []
while right < n:
while right < n and right - left < k:
if arr[right] < 0:
negatives.append((right, arr[right]))
right += 1
result.append(negatives[0][1] if negatives else 0)
if negatives and negatives[0][0] == left:
negatives.popleft()
left += 1
return result
Sorting
1984. Minimum Difference Between Highest and Lowest of K Scores
Easy·
Solutions:
Visualize
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
left = right = 0
mini = float("inf")
while right < n:
# Expansion
while right < n and right - left < k:
right += 1
# Logic
mini = min(mini, nums[right - 1] - nums[left])
# Shrinking
left += 1
return mini
Bit Manipulation
3023. Find Pattern in Infinite Stream I
Medium·
Solutions:
Visualize
# Definition for an infinite stream.
# class InfiniteStream:
# def next(self) -> int:
# pass
class Solution:
def findPattern(
self, stream: Optional["InfiniteStream"], pattern: List[int]
) -> int:
k = len(pattern)
left = right = 0
pattern_num = 0
for num in pattern:
pattern_num = pattern_num << 1 | num
stream_num = 0
mask = 1 << (k - 1)
while True:
# Expansion
while right - left < k:
stream_num = stream_num << 1 | stream.next()
right += 1
# Logic
if pattern_num == stream_num:
return left
# Shrinking: Trim the left most (most significant) bit
# stream_num = stream_num & ~(mask) # Approach 1 - industry standard
# Approach 2 - sidesteps Python's negative number/two's complement behavior
stream_num = (stream_num | mask) ^ mask
left += 1
return 0
3037. Find Pattern in Infinite Stream II
Hard·
Solutions:
Visualize
# Definition for an infinite stream.
# class InfiniteStream:
# def next(self) -> int:
# pass
class Solution:
def findPattern(
self, stream: Optional["InfiniteStream"], pattern: List[int]
) -> int:
k = len(pattern)
left = right = 0
pattern_num = 0
for num in pattern:
pattern_num = pattern_num << 1 | num
stream_num = 0
mask = 1 << (k - 1)
while True:
# Expansion
while right - left < k:
stream_num = stream_num << 1 | stream.next()
right += 1
# Logic
if pattern_num == stream_num:
return left
# Shrinking: Trim the left most (most significant) bit
# stream_num = stream_num & ~(mask) # Approach 1 - industry standard
# Approach 2 - sidesteps Python's negative number/two's complement behavior
stream_num = (stream_num | mask) ^ mask
left += 1
return 0
Miscellaneous
30. Substring with Concatenation of All Words
Hard·
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 findSubstring(self, s: str, words: List[str]) -> List[int]:
n = len(s)
w = len(words[0])
k = w * len(words)
result = []
for i in range(w):
left = right = i
counter = Counter(words)
while right < n:
while right < n and right - left < k:
counter[s[right : right + w]] -= 1
right += w
if counter.distinct_count() == 0:
result.append(left)
counter[s[left : left + w]] += 1
left += w
return result