აღწერეთ ალგორითმი ყველა უნიკალური სიმბოლოსთან ერთად სუბსტრინგების რაოდენობისთვის

ერთგვარი სიმბოლოებით შემდგარი ქვესაწყვეტილების რაოდენობის გამოთვლისთვის ჩვეულებრივ იყენებენ "გადმოსვლის ფანჯრის" (sliding window) ალგორითმს. იდეა მდგომარეობს იმაში, რომ შეინარჩუნოს ფანჯარა, რომელშიც ყველა სიმბოლო უნიკალურია, და გადაადგილოს ის სტრიქონზე, ითვლით ამგვარი ქვესაწყვეტილების რაოდენობას.

ძირითადი ნაბიჯები:

1. გამოიყენეთ ორი მაჩვენებელი — left და right, რომლებიც განსაზღვრავენ ფანჯრის საზღვრებს.
2. გამოიყენეთ მონაცემთა სტრუქტურა (მაგ., რუკა ან მასივი) შეხვედგა სიმბოლოებს და მათი რაოდენობა.
3. გაფართოვეთ ფანჯარა მარჯვნივ, დაამატეთ სიმბოლოები, სანამ ყველა უნიკალურია.
4. თუ გამოჩნდა განმეორებითი სიმბოლო, გადაადგილეთ მარცხენა მაჩვენებელი მარჯვნივ, შემცირებით სიმბოლოების გამოთვლებს, სანამ განმეორება არ გაქრება.
5. ყოველ ნაბიჯზე, შეგიძლიათ ითვალეთ უნიკალური ქვესაწყვეტილების რაოდენობა, მაგალითად, დამატებით right - left + 1.

მაგალითი 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
}

აქ, count წარმოადგენს უნიკალური სიმბოლოებით შემდგარი ქვესაწყვეტილების საერთო რაოდენობას.