Αυτή είναι μια σειρά χαρακτήρων. Βρείτε τον αριθμό των ζευγών δεικτών i και j (i <= j), μεταξύ των οποίων, συμπεριλαμβανομένων, δεν υπάρχουν επαναλαμβανόμενοι χαρακτήρες. Για τη σειρά "aba" η απάντηση είναι 5: [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") Για τη σειρά "acbb" η απάντηση είναι ?:

Για τη συμβολοσειρά "acbb" πρέπει να βρούμε τον αριθμό των ζευγών δεικτών [i, j] (i ≤ j), τέτοια ώστε η υπο-συμβολοσειρά s[i..j] να περιέχει μόνο μοναδικούς χαρακτήρες.

Ας αναλύσουμε τη συμβολοσειρά "acbb":

• [0,0] = "a" — μοναδικό
• [0,1] = "ac" — μοναδικό
• [0,2] = "acb" — μοναδικό
• [0,3] = "acbb" — επανάληψη "b", όχι έγκυρο
• [1,1] = "c" — μοναδικό
• [1,2] = "cb" — μοναδικό
• [1,3] = "cbb" — επανάληψη "b", όχι έγκυρο
• [2,2] = "b" — μοναδικό
• [2,3] = "bb" — επανάληψη "b", όχι έγκυρο
• [3,3] = "b" — μοναδικό

Συνολικά, υπάρχουν 7 τέτοια ζεύγη.

Μπορείτε να λύσετε το πρόβλημα χρησιμοποιώντας δύο δείκτες και ένα σύνολο για την παρακολούθηση των μοναδικών χαρακτήρων:

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
}

// Παράδειγμα χρήσης:
// fmt.Println(countUniqueSubstrings("acbb")) // Θα εμφανίσει 7

Αυτός ο αλγόριθμος λειτουργεί σε χρόνο O(n), όπου n είναι το μήκος της συμβολοσειράς.