Förberedelse inför kodningsintervjuer · Lektion

Längsta delsträng utan upprepningar

Följ senast sedda positioner i ett fönster

Lektion 3 av 413 steg

Längsta delsträng utan upprepningar är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Ett klassiskt fönsterproblem

Hitta den längsta delsträngen utan upprepade tecken. Det är ett klassiskt problem för glidande fönster som dyker upp på nästan alla tävlingsplattformar. 🔤

Brute force-fällan

Att kontrollera varje delsträng efter dubbletter kostar ungefär O(n^2) eller mer. För långa strängar är det alldeles för långsamt, så en smartare genomgång behövs.

Fönster med unika tecken

Håll ett fönster som alltid innehåller unika tecken. Utöka det åt höger och krymp det från vänster när en upprepning uppstår, tills upprepningen är borta.

Kom ihåg de senaste positionerna

Spara varje teckens senaste index i en dictionary. Då vet du direkt var en upprepning senast förekom när du går igenom strängen.

last = {}
left = 0
best = 0

Gå igenom varje tecken

Iterera med right över strängen och läs både indexet och tecknet vid varje steg. På så sätt flyttas fönstret framåt en position i taget.

for right, ch in enumerate(s):

Hoppa med left-pekaren

Om tecknet har setts inne i det aktuella fönstret flyttar du left till precis efter dess senaste position. Då tas dubbletten bort i ett enda steg.

    if ch in last and last[ch] >= left:
        left = last[ch] + 1

Uppdatera och mät

Spara tecknets nya position. Därefter är fönstret från left till right fritt från dubbletter. Dess längd är right minus left plus one.

    last[ch] = right
    best = max(best, right - left + 1)

Därför är kontrollen viktig

Kontrollen last[ch] >= left är avgörande. Utan den skulle en gammal position utanför fönstret felaktigt flytta left bakåt.

Linjär tid, linjärt utrymme

Varje tecken besöks en gång och left rör sig bara framåt, så genomgången är O(n). Dictionary använder utrymme för de unika tecknen.

Täck kantfallen

En tom sträng ger svaret noll, och en sträng med en enda upprepad bokstav ger svaret ett. Kontrollera båda innan du skickar in lösningen för att undvika ett lurigt WA.

Det återanvändbara mönstret

En map över senast sedda positioner tillsammans med en left-pekare som hoppar fram kan generaliseras till många problem med unika värden, till exempel fönster med högst en upprepning.

Snabb kontroll

Du håller reda på varje teckens senaste index när du söker efter den längsta delsträngen utan upprepade tecken.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Flytta ett fönster med unika tecken, spara varje senaste position och hoppa med left förbi upprepningar. Det löser det klassiska problemet på O(n). ✅

Gratis att börja

Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 90
Lektioner: 360

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Längsta delsträng utan upprepningar” gratis?

Ja – hela texten till ”Längsta delsträng utan upprepningar” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Vad lär jag mig i ”Längsta delsträng utan upprepningar”?

Följ senast sedda positioner i ett fönster Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?

Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.

Hur lång tid tar lektionen ”Längsta delsträng utan upprepningar”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?

Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Förberedelse inför kodningsintervjuer