Bu matn satridir. I va j indeks juftliklarining sonini toping (i <= j), ular orasida, shu jumladan, takrorlanmaydigan belgilar bo'lmagan. "aba" satri uchun javob 5: [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") "acbb" satri uchun javob ?:

"acbb" satr uchun, s[i..j] kichik harflaridan iborat bo'lgan va faqat unikal belgilarni o'z ichiga olgan indekslar juftligini topish kerak.

"acbb" satrini tahlil qilamiz:

• [0,0] = "a" — unikal
• [0,1] = "ac" — unikal
• [0,2] = "acb" — unikal
• [0,3] = "acbb" — takror "b", mos emas
• [1,1] = "c" — unikal
• [1,2] = "cb" — unikal
• [1,3] = "cbb" — takror "b", mos emas
• [2,2] = "b" — unikal
• [2,3] = "bb" — takror "b", mos emas
• [3,3] = "b" — unikal

Jami 7 ta juftlik.

Bu muammoni ikki ko'rsatkich va unikal belgilarni kuzatish uchun to'plam yordamida hal qilish mumkin:

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

// Misol uchun:
// fmt.Println(countUniqueSubstrings("acbb")) // 7 ni chiqaradi

Ushbu algoritm, satr uzunligi n bo'lsa, O(n) vaqt ichida ishlaydi.