Aprakstiet algoritmu, kā skaitīt apakšvirknes ar visiem unikālajiem simboliem

Skaitot skaitu, cik daudz apakšvirkņu ar unikāliem rakstzīmēm, parasti izmanto "slīdējo logu" (sliding window) algoritmu. Ideja ir uzturēt logu, kurā visi rakstzīmes ir unikālas, un to pārvietot pa virkni, skaitot šādu apakšvirkņu skaitu.

Galvenie soļi:

1. Izmantojiet divus rādītājus — left un right, kas nosaka loga robežas.
2. Izmantojiet datu struktūru (piemēram, karti vai masīvu), lai sekotu sastaptajām rakstzīmēm un to skaitam.
3. Paplašiniet logu pa labi, pievienojot rakstzīmes, kamēr tās visas ir unikālas.
4. Ja parādās atkārtojoša rakstzīme, pārvietojiet kreiso rādītāju pa labi, samazinot rakstzīmju skaitus, līdz atkārtošanās izzūd.
5. Katru soli var skaitīt unikālo apakšvirkņu skaitu, piemēram, pievienojot right - left + 1.

Piemērs Go valodā:

func countUniqueSubstrings(s string) int {
    freq := make(map[rune]int)
    left, count := 0, 0
    for right, ch := range s {
        freq[ch]++
        for freq[ch] > 1 {
            freq[rune(s[left])]--
            left++
        }
        count += right - left + 1
    }
    return count
}

Šeit count apzīmē kopējo unikālo rakstzīmju apakšvirkņu skaitu.