Given a string S, count the number of substrings in this string that contain all characters from this string at least once. Examples: "abca" -> 3 // abc, bca, abca "aa" -> 3 // aa, a, a, "ffg" -> 2 // ffg, fg

To solve the problem, you need to find the number of substrings that contain all the unique characters of the original string at least once.

Approach:

1. Determine the set of unique characters in the original string.
2. Use two pointers (two-pointer sliding window) to iterate over substrings.
3. Expand the right pointer until the substring contains all unique characters.
4. Then, shift the left pointer, reducing the substring, and count the number of suitable substrings.

Example implementation in Go:

func countSubstringsWithAllChars(s string) int {
    uniqueChars := make(map[rune]struct{})
    for _, ch := range s {
        uniqueChars[ch] = struct{}{}
    }
    required := len(uniqueChars)

    windowCounts := make(map[rune]int)
    have := 0
    res := 0
    left := 0

    runes := []rune(s)

    for right, ch := range runes {
        windowCounts[ch]++
        if windowCounts[ch] == 1 { // first time encountering this character in the window
            have++
        }

        for have == required {
            // All unique characters are in the substring runes[left:right+1]
            // All substrings starting at left and ending at right or further are suitable
            res += len(runes) - right

            // Move the left pointer
            windowCounts[runes[left]]--
            if windowCounts[runes[left]] == 0 {
                have--
            }
            left++
        }
    }

    return res
}

This algorithm runs in O(n), where n is the length of the string, since each character is processed at most twice.