Sliding window voor substrings
Implementeer een sliding window met variabele grootte om de langste substring zonder herhaalde tekens en het kleinste venster met alle doeltekens te vinden.
Sliding window voor substrings is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 2 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Het concept van het schuivende venster
Een schuivend venster houdt een deelarray (of deeltekenreeks) bij tussen een linker- en rechteraanwijzer. In plaats van de eigenschappen van elke mogelijke deelarray telkens opnieuw te berekenen in O(n²), breidt het venster rechts uit door één element toe te voegen en krimpt het links door één element te verwijderen, terwijl het bijhouden van de toestand per stap O(1) kost. Het resultaat is een algoritme van O(n). Het venster heet schuivend omdat het vooruit door de array beweegt zonder terug te gaan.
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])Vaste versus variabele venstergrootte
Er zijn twee varianten van het schuivende venster. Bij een venster met vaste grootte gaan beide aanwijzers even snel vooruit en bevat het venster altijd precies k elementen. Bij een venster met variabele grootte breidt de rechteraanwijzer zich gretig uit en krimpt de linkeraanwijzer alleen wanneer het venster een beperking schendt. Vensters met variabele grootte lossen problemen op zoals de langste deeltekenreeks zonder herhalende tekens, waarbij de optimale venstergrootte vooraf onbekend is.
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2Langste deeltekenreeks zonder herhalingen
Dit is het bekendste probleem met een variabel schuivend venster. Gebruik een set om de tekens in het huidige venster bij te houden. Breid rechts uit; zodra je een duplicaat vindt, krimp je vanaf links totdat het duplicaat is verwijderd. Een snellere versie gebruikt een hashmap met de laatste index van elk teken, zodat de linkeraanwijzer in één stap voorbij het duplicaat kan springen in plaats van stap voor stap vooruit te schuiven.
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')Kleinste venster voor een deeltekenreeks
Gegeven de tekenreeksen s en t: vind het kleinste venster in s dat alle tekens van t bevat. Gebruik twee frequentiemaps: need (vereiste tekens) en have (tekens in het huidige venster die aan de vereiste voldoen). Houd bij aan hoeveel unieke tekens van t is voldaan (formed-teller). Breid rechts uit om tekens op te nemen; wanneer heel t is gedekt, krimp je links om het venster te minimaliseren. Tijd: O(|s| + |t|).
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'Sjabloon voor het schuivende venster
De meeste problemen met een venster van variabele grootte volgen hetzelfde sjabloon: breid rechts uit om het nieuwe teken op te nemen, werk de toestand van het venster bij, controleer de geldigheid en krimp het venster vanaf links als het ongeldig is totdat het weer geldig is. Het belangrijkste inzicht is dat de linkeraanwijzer alleen vooruitgaat — hij gaat nooit terug — waardoor al het werk van alle krimpstappen samen O(n) kost. Het venster bezoekt elk element hoogstens twee keer: één keer bij het toevoegen en één keer bij het verwijderen.
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return bestPermutatie in een tekenreeks
Controleer of een permutatie van patroon p als deeltekenreeks van s voorkomt. Een permutatiecontrole komt overeen met een venster met dezelfde tekenfrequenties als p. Houd een schuivend venster van precies len(p) tekens bij en vergelijk de frequentietellingen. Het vergelijken van volledige Counter-objecten kost per stap O(26) (constant voor kleine Engelse letters), wat in totaal O(n × 26) = O(n) oplevert.
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # FalseAlle anagrammen in deeltekenreeksen tellen
Vind alle startindexen van anagrammen van p in s. Dit is dezelfde techniek met een venster van vaste grootte als bij een permutatie in een tekenreeks, maar in plaats van bij de eerste overeenkomst True terug te geven, verzamelen we alle overeenkomende posities. De venstergrootte is vast op len(p); we schuiven het venster over s en vergelijken bij elke stap de frequentietellingen.
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]Langste deeltekenreeks met hoogstens 2 verschillende tekens
Een variant van het schuivende venster: vind de langste deeltekenreeks met hoogstens 2 verschillende tekens. Houd een frequentiemap bij van de tekens in het huidige venster. Zodra de map meer dan 2 items bevat, verplaats je de linkeraanwijzer naar rechts, verlaag je de frequentie en verwijder je het teken als de frequentie nul wordt, totdat weer aan de beperking is voldaan. Dit is een speciaal geval van hoogstens k verschillende tekens, met k=2.
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')Maximum van een schuivend venster
Vind het maximum in elk venster met grootte k. Bij een uitputtende controle van het maximum van elk venster kost dit O(n×k). De optimale aanpak gebruikt een monotone deque met indexen: houd een aflopende deque bij, zodat de voorkant altijd de index van het maximum van het huidige venster bevat. Verwijder indexen aan de voorkant zodra ze het venster verlaten en verwijder indexen aan de achterkant wanneer er een groter element binnenkomt. Totale tijd: O(n).
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Wanneer je een schuivend venster gebruikt
Gebruik een schuivend venster wanneer je dit ziet:
- Deeltekenreeks of deelarray met een beperking (maximale lengte, som = k, hoogstens k verschillende tekens)
- Vaste venstergrootte met een aggregatie (maximum, som, frequentie)
- Vragen over aaneengesloten bereiken (geen willekeurige deelverzamelingen)
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2Geldige vensters tellen: hoogstens K
Sommige problemen vragen om het aantal deelarrays te tellen dat aan een voorwaarde voldoet. Een handige truc is: tel deelarrays met hoogstens k verschillende tekens en trek die af om precies k te krijgen: exactly(k) = at_most(k) - at_most(k-1). Elke aanroep van at_most kost O(n), dus in totaal kost dit O(n). De functie at_most telt vensters waarin het aantal verschillende tekens niet groter is dan k door right - left + 1 op te tellen (alle geldige linker eindpunten voor elke rechteraanwijzer).
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9Korte controle
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep die in deze les aan bod komen.
Samenvatting van de les
In deze les heb je geleerd: het schuivende venster voorkomt O(n²) door een lopende venstertoestand bij te houden die in O(1) wordt bijgewerkt wanneer elementen binnenkomen en vertrekken, vensters met vaste grootte verplaatsen beide aanwijzers even snel; vensters met variabele grootte breiden rechts gretig uit en krimpen links alleen wanneer een beperking wordt geschonden, en het kleinste venster voor een deeltekenreeks en een permutatie in een tekenreeks gebruiken beide de toestand van een venster met frequentiemaps, met een teller die bijhoudt aan hoeveel vereiste tekens momenteel is voldaan. Hierna verkennen we anagrammen en frequentiemaps voor tekens.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Sliding window voor substrings” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Sliding window voor substrings”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “Sliding window voor substrings”?
Implementeer een sliding window met variabele grootte om de langste substring zonder herhaalde tekens en het kleinste venster met alle doeltekens te vinden. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Sliding window voor substrings”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Python String API voor interviews
- Sliding window voor substrings
- Anagrammen en frequentiemaps voor tekens
- Stringcodering, omkeren en palindromen