func countSubs(s string) int { result := 0 left := 0 hm := make(map[rune]int) for right := 0; right < len(s); right++ { hm[s[right]]++ for hm[s[right]] > 1 { hm[s[left]]-- if hm[s[left]] == 0 { delete(hm, s[left]) } left++ } result += (right - left + 1) } return result }

Funkcia countSubs spočíta počet podreťazcov v reťazci s, v ktorých sú všetky znaky unikátne.

Algoritmus využíva metódu "kĺzavého okna" so dvoma ukazovateľmi left a right. Slovník hm uchováva počet výskytov jednotlivých znakov v aktuálnom okne.

• Pri rozširovaní okna doprava zvyšujeme čítač znaku.
• Ak sa znak vyskytuje viackrát, posunieme ľavý ukazovateľ, znižujúc počty, kým sa opakovanie neztratí.
• Počet unikátnych podreťazcov končiacich na pozícii right je rovný dĺžke aktuálneho okna (right - left + 1).
• Tento počet sčítavame ku všetkým pozíciám.

Príklad použitia:

total := countSubs("abc") // total = 6, podreťazce: "a", "b", "c", "ab", "bc", "abc"

Týmto spôsobom funkcia efektívne počíta počet podreťazcov bez opakujúcich sa znakov v čase O(n).