Սա նիշերի շղթա է։ Գտեք 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 տեքստի երկարությունն է։