Sliding window for delstrenger
Implementer et sliding window med variabel størrelse for å finne den lengste delstrengen uten gjentatte tegn og det minste vinduet som inneholder alle måltegn.
Sliding window for delstrenger er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Konseptet med glidende vindu
Et glidende vindu opprettholder et delarray (eller en delstreng) mellom en venstre- og en høyrepeker. I stedet for å beregne egenskapene til hvert mulig delarray på nytt fra grunnen av i O(n²), utvides vinduet mot høyre ved å legge til ett element og trekkes sammen mot venstre ved å fjerne ett element, samtidig som en løpende tilstand opprettholdes i O(1) per trinn. Resultatet er en algoritme på O(n). Vinduet kalles «glidende» fordi det beveger seg fremover gjennom arrayet uten å gå bakover.
# 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 vindusstørrelse
Det finnes to varianter av glidende vindu. I et vindu med fast størrelse går begge pekerne frem i samme tempo, og vinduet har alltid nøyaktig k elementer. I et vindu med variabel størrelse utvides høyrepekereren grådig, mens venstrepekeren bare trekker seg sammen når vinduet bryter en begrensning. Vinduer med variabel størrelse løser problemer som «lengste delstreng uten gjentatte tegn», der den optimale vindusstørrelsen ikke er kjent 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)) # 2Lengste delstreng uten gjentakelser
Dette er det mest kjente problemet med variabelt glidende vindu. Bruk et sett til å holde oversikt over tegnene i det aktuelle vinduet. Utvid mot høyre. Når et duplikat oppdages, krymper du fra venstre til duplikatet er fjernet. En raskere variant bruker en hashtabell som lagrer den nyeste indeksen for hvert tegn, slik at venstrepekeren kan hoppe forbi duplikatet i ett trinn i stedet for å flyttes gradvis.
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')Minste vindu i en streng
Gitt strengene s og t skal du finne det minste vinduet i s som inneholder alle tegnene i t. Bruk to frekvenstabeller: need (tegn som kreves) og have (tegn i det aktuelle vinduet som oppfyller kravet). Hold oversikt over hvor mange unike tegn i t som er oppfylt (formed-telleren). Utvid mot høyre for å ta med tegn. Når hele t er dekket, krymper du fra venstre for å gjøre vinduet minst mulig. Tidskompleksitet 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'Mal for glidende vindu
De fleste problemer med variabelt glidende vindu følger samme mal: utvid mot høyre for å ta med det nye tegnet, oppdater vindustilstanden, kontroller gyldigheten, og krymp fra venstre hvis vinduet er ugyldig, til det blir gyldig igjen. Den viktige innsikten er at venstrepekeren bare beveger seg fremover — den går aldri bakover — så det totale arbeidet for alle krympetrinnene er O(n). Vinduet besøker hvert element høyst to ganger (én gang når det legges til, 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 bestPermutasjon i streng
Kontroller om en hvilken som helst permutasjon av mønsteret p finnes som en delstreng i s. En permutasjonssjekk tilsvarer et vindu med samme tegnfrekvens som p. Oppretthold et glidende vindu med nøyaktig len(p) tegn, og sammenlign frekvenstellingene. Det koster O(26) å sammenligne hele Counter-objekter for hvert trinn (konstant for engelske små bokstaver), noe som gir O(n × 26) = O(n) totalt.
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')) # FalseAnagramdelstrenger: tell alle
Finn alle startindeksene til anagrammene av p i s. Dette er den samme teknikken med fast vindu som for permutasjon i streng, men i stedet for å returnere True ved første treff samler vi alle treffposisjonene. Vindusstørrelsen er fast på len(p). Vi flytter vinduet gjennom s og sammenligner frekvenstellingene ved hvert trinn.
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]Lengste delstreng med høyst 2 ulike tegn
En variant av glidende vindu: Finn den lengste delstrengen som inneholder høyst 2 ulike tegn. Oppretthold en frekvenstabell over tegnene i det aktuelle vinduet. Når tabellen inneholder mer enn 2 oppføringer, flytter du venstrepekeren mot høyre (reduser frekvensen og slett oppføringen hvis den blir null) til begrensningen igjen er oppfylt. Dette er et spesialtilfelle av «høyst k ulike 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 vindu
Finn maksimumet i hvert vindu med størrelse k. En brute force-sjekk av maksimumet i hvert vindu tar O(n×k). Den optimale løsningen bruker en monoton deque med indekser: Oppretthold en avtakende deque slik at fronten alltid inneholder indeksen til maksimumet i det aktuelle vinduet. Fjern indekser fra fronten når de forlater vinduet, og fjern indekser fra baksiden når et større element kommer inn. Total tidskompleksitet 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]Når skal glidende vindu brukes
Bruk glidende vindu når du ser:
- Delstreng eller delarray med en begrensning (maksimal lengde, sum = k, høyst k ulike tegn)
- Fast vindusstørrelse med en aggregering (maksimum, sum, frekvens)
- Spørsmål om sammenhengende områder (ikke vilkårlige delmengder)
# 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])) # 2Tell gyldige vinduer: høyst K
Noen problemer spør etter antallet delarrayer som oppfyller en betingelse. Et nyttig triks er å telle delarrayer med høyst k ulike tegn og deretter trekke fra for å få nøyaktig k: exactly(k) = at_most(k) - at_most(k-1). Hvert kall til at_most er O(n), så totalen blir O(n). Funksjonen at_most teller vinduer der antallet ulike tegn ikke overstiger k, ved å summere right - left + 1 (alle gyldige venstreendepunkter for hver høyreende).
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)) # 9Hurtigsjekk
Test forståelsen av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte du at: glidende vindu eliminerer O(n²) ved å opprettholde en løpende vindustilstand som oppdateres i O(1) når elementer kommer inn og forlater vinduet, vinduer med fast størrelse flytter begge pekerne i samme tempo, mens vinduer med variabel størrelse utvides grådig mot høyre og bare trekkes sammen mot venstre når en begrensning brytes, og minimum window substring og permutation-in-string begge bruker vindustilstand med frekvenstabeller og en teller som holder oversikt over hvor mange påkrevde tegn som for øyeblikket er oppfylt. Neste gang skal vi utforske anagrammer og frekvenstabeller for tegn.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Sliding window for delstrenger» gratis?
Ja – hele teksten i «Sliding window for delstrenger» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Sliding window for delstrenger»?
Implementer et sliding window med variabel størrelse for å finne den lengste delstrengen uten gjentatte tegn og det minste vinduet som inneholder alle måltegn. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Sliding window for delstrenger»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Pythons streng-API for intervjuer
- Sliding window for delstrenger
- Anagrammer og frekvenskart for tegn
- Strengkoding, reversering og palindromer