Sliding window til substrings
Implementer et sliding window i variabel størrelse for at finde den længste substring uden gentagne tegn og det mindste vindue, der indeholder alle måltegn.
Sliding window til substrings er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Begrebet glidende vindue
Et glidende vindue vedligeholder et delarray (eller en delstreng) mellem en venstre og en højre markør. I stedet for at genberegne egenskaberne for hvert muligt delarray fra bunden i O(n²) udvides vinduet mod højre ved at tilføje ét element, og det trækkes sammen mod venstre ved at fjerne ét element, mens en løbende tilstand vedligeholdes i O(1) pr. trin. Resultatet er en algoritme i O(n). Vinduet kaldes glidende, fordi det bevæger sig fremad gennem arrayet uden at gå tilbage.
# 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])Fast eller variabel vinduesstørrelse
Der findes to varianter af glidende vinduer. I et vindue med fast størrelse bevæger begge markører sig i samme tempo, og vinduet indeholder altid præcis k elementer. I et vindue med variabel størrelse udvides den højre markør grådigt, mens den venstre markør kun trækker vinduet sammen, når det overtræder en begrænsning. Vinduer med variabel størrelse løser problemer som 'længste delstreng uden gentagne tegn', hvor den optimale vinduesstørrelse ikke er kendt på forhånd.
# 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)) # 2Længste delstreng uden gentagelser
Det mest berømte problem med et variabelt glidende vindue. Brug en mængde til at holde styr på tegnene i det aktuelle vindue. Udvid mod højre; når du finder et gentaget tegn, skal du formindske vinduet fra venstre, indtil det gentagne tegn er fjernet. En hurtigere version bruger en hash-tabel, der gemmer det seneste indeks for hvert tegn, så den venstre markør kan springe forbi det gentagne tegn i ét trin i stedet for at bevæge sig frem ét trin ad gangen.
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')Mindste delstrengsvindue
Givet strengene s og t skal du finde det mindste vindue i s, der indeholder alle tegnene i t. Brug to frekvenskort: need (krævede tegn) og have (tegn i det aktuelle vindue, der opfylder kravet). Hold styr på, hvor mange forskellige tegn i t der er opfyldt (formed-tælleren). Udvid mod højre for at inkludere tegn; når hele t er dækket, skal du formindske vinduet fra venstre for at minimere det. Køretid 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'Skabelon til glidende vindue
De fleste problemer med variable glidende vinduer følger den samme skabelon: udvid mod højre for at inkludere det nye tegn, opdatér vinduestilstanden, tjek gyldigheden, og formindsk vinduet fra venstre, hvis det er ugyldigt, indtil det igen er gyldigt. Den vigtige indsigt er, at den venstre markør kun bevæger sig fremad — den går aldrig tilbage — så det samlede arbejde på tværs af alle trin, hvor vinduet formindskes, er O(n). Vinduet besøger hvert element højst to gange (én gang, når det tilføjes, og én gang, når det fjernes).
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 bestPermutation i en streng
Tjek, om en permutation af mønsteret p findes som en delstreng i s. Et permutationstjek svarer til et vindue med samme tegnfrekvens som p. Vedligehold et glidende vindue med præcis len(p) tegn, og sammenlign frekvenstællingerne. Det koster O(26) at sammenligne hele Counter-objekter ved hvert trin (konstant for små engelske bogstaver), hvilket giver O(n × 26) = O(n) samlet.
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')) # FalseAnagram-delstrenge: Tæl alle
Find alle startindekser for anagrammer af p i s. Det er den samme teknik med et vindue med fast størrelse som ved permutationer i strenge, men i stedet for at returnere True ved det første match samler vi alle matchende positioner. Vinduesstørrelsen er fast på len(p); lad det glide hen over s, og sammenlign frekvenstællingerne ved hvert trin.
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]Længste delstreng med højst 2 forskellige tegn
En variant af glidende vindue: Find den længste delstreng, der indeholder højst 2 forskellige tegn. Vedligehold et frekvenskort over tegnene i det aktuelle vindue. Når kortet indeholder mere end 2 poster, skal du flytte den venstre markør mod højre (sænk frekvensen, og slet posten, hvis den er nul), indtil begrænsningen igen er opfyldt. Dette er et specialtilfælde af 'højst k forskellige tegn' med 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')Maksimum i glidende vindue
Find maksimumværdien i hvert vindue med størrelse k. En udtømmende kontrol af maksimumværdien i hvert vindue koster O(n×k). Den optimale tilgang bruger en monoton dobbeltsidet kø af indekser: vedligehold en faldende kø, så det forreste element altid er indekset for det aktuelle vindues maksimum. Fjern indekser fra forrest, når de forlader vinduet, og fjern indekser bagfra, når et større element kommer ind. Den samlede køretid er 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]Hvornår skal du bruge glidende vindue
Brug det glidende vindue, når du ser:
- En delstreng eller et delarray med en begrænsning (maksimal længde, sum = k, højst k forskellige tegn)
- En fast vinduesstørrelse med en aggregering (maksimum, sum, frekvens)
- Spørgsmål om sammenhængende intervaller (ikke vilkårlige delmængder)
# 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])) # 2Tæl gyldige vinduer: højst K
Nogle problemer spørger, hvor mange delarrays der opfylder en betingelse. En nyttig teknik er at tælle delarrays med højst k forskellige tegn og derefter trække fra for at få præcis k: exactly(k) = at_most(k) - at_most(k-1). Hvert kald til at_most tager O(n), så den samlede køretid er O(n). Funktionen at_most tæller vinduer, hvor antallet af forskellige tegn ikke overstiger k, ved at summere right - left + 1 (alle gyldige venstre endepunkter for hvert højre endepunkt).
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)) # 9Hurtigt tjek
Tjek din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Lektionsopsamling
I denne lektion lærte du: det glidende vindue eliminerer O(n²) ved at vedligeholde en løbende vinduestilstand, der opdateres i O(1), når elementer kommer ind og forlader vinduet, vinduer med fast størrelse flytter begge markører i samme tempo; vinduer med variabel størrelse udvides grådigt mod højre og trækkes kun sammen mod venstre, når en begrænsning overtrædes, og mindste delstrengsvindue og permutation i en streng bruger begge vinduestilstand med frekvenskort samt en tæller, der holder styr på, hvor mange krævede tegn der aktuelt er opfyldt. Nu skal vi se på anagrammer og frekvenskort over tegn.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Sliding window til substrings” gratis?
Ja — hele teksten til “Sliding window til substrings” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Sliding window til substrings”?
Implementer et sliding window i variabel størrelse for at finde den længste substring uden gentagne tegn og det mindste vindue, der indeholder alle måltegn. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Sliding window til substrings”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Pythons string-API til interviews
- Sliding window til substrings
- Anagrammer og tegnfrekvenskort
- Strengkodning, vending og palindromer