func countSubs(s string) int { result := 0 left := 0 hm := make(map[rune]int) n := len(s) for right := 0; right < n; 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 }

Táto funkcia v Go počíta počet podreťazcov v reťazci s, v ktorých sú všetky znaky jedinečné.

Ako to funguje:

• Používa sa posuvné okno s hranicami left a right.
• V hm je uložený počet výskytov každého znaku v aktuálnom okne.
• Pri rozšírení okna doprava sa zvyšuje čítač znaku.
• Ak sa znak objaví viackrát, posúvame ľavú hranicu okna, znižujúc počítadlá, kým všetky znaky nebudú jedinečné.
• Počet jedinečných podreťazcov končiacich na pozícii right je rovný dĺžke aktuálneho okna (right - left + 1).
• Tento počet sa sčíta pre všetky pozície.

Príklad:

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

Týmto spôsobom funkcia efektívne počíta počet podreťazcov s jedinečnými znakmi v čase O(n).