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 }

Αυτή η λειτουργία σε Go μετράει τον αριθμό των υποσυνόλων στη συμβολοσειρά s όπου όλα τα σύμβολα είναι μοναδικά.

Πώς λειτουργεί:

• Χρησιμοποιείται ένα κινούμενο παράθυρο με όρια left και right.
• Στο hm αποθηκεύεται ο αριθμός των εμφανίσεων κάθε συμβόλου στο τρέχον παράθυρο.
• Καθώς επεκτείνεται το παράθυρο προς τα δεξιά, αυξάνεται ο μετρητής του συμβόλου.
• Αν ένα σύμβολο εμφανίζεται περισσότερες από μία φορές, μετακινούμε το αριστερό όριο του παραθύρου, μειώνοντας τους μετρητές, μέχρι όλα τα σύμβολα να είναι μοναδικά.
• Ο αριθμός των μοναδικών υποσυνόλων που τελειώνουν στη θέση right είναι ίσος με το μήκος του τρέχοντος παραθύρου (right - left + 1).
• Προσθέτουμε αυτό το ποσό σε όλες τις θέσεις.

Παράδειγμα:

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
}

Έτσι, η λειτουργία μετρά αποτελεσματικά τον αριθμό των υποσυνόλων με μοναδικά σύμβολα σε χρόνο O(n).