Popíšte algoritmus na riešenie úlohy počítania podreťazcov so všetkými jedinečnými znakmi

Na výpočet počtu podreťazcov s unikátnymi znakmi sa zvyčajne používa algoritmus "posuvného okna" (sliding window). Myšlienka spočíva v tom, že udržiavame okno, v ktorom sú všetky znaky jedinečné, a posúvame ho pozdĺž reťazca, počítajúc počet takýchto podreťazcov.

Hlavné kroky:

1. Použiť dva ukazovatele — left a right, ktoré určujú hranice okna.
2. Použiť dátovú štruktúru (napríklad mapu alebo pole) na sledovanie stretnutých znakov a ich počtu.
3. Rozšíriť okno doprava, pridávaním znakov, pokiaľ sú všetky jedinečné.
4. Ak sa objaví opakujúci sa znak, posunúť ľavý ukazovateľ doprava, znižujúc počty znakov, kým opakovanie nezmizne.
5. Pri každom kroku možno počítať počet unikátnych podreťazcov, napríklad pridaním right - left + 1.

Príklad v Go:

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
}

Tu count predstavuje celkový počet podreťazcov s unikátnymi znakmi.