Problem

Given a string s, count the number of substrings (contiguous, non-empty) in which all characters are distinct.

Input / Output

• Input: string s of lowercase letters (or ASCII).
• Output: the count (may exceed 32 bits for long strings).

Examples

Example 1 Input: s = "abc" Output: 6 Explanation: a, b, c, ab, bc, abc — every substring has distinct characters.

Example 2 Input: s = "aab" Output: 4 Explanation: a, a, b, ab. The substrings aa and aab repeat a.

Example 3 Input: s = "abab" Output: 7 Explanation: a, b, a, b, ab, ba, ab.

Constraints

• 1 <= s.length <= 10^5

Approach — Sliding window

Fix the right end r and maintain the smallest l such that s[l..r] has no repeated character. Every substring ending at r and starting at any index in [l, r] is valid, so add r - l + 1 to the answer.

Maintain last[c] = the most recent index of character c:

l = 0; ans = 0; last = {}
for r in 0..n-1:
    if s[r] in last and last[s[r]] >= l:
        l = last[s[r]] + 1
    last[s[r]] = r
    ans += r - l + 1

Because l only moves forward, the whole scan is linear. A frequency array plus a while loop that shrinks the window until freq[s[r]] == 1 is an equivalent formulation.

Complexity

• Time: O(n)
• Space: O(alphabet size)

Relationship to other problems

This is "Longest Substring Without Repeating Characters" with a different accumulation step: instead of max(len) you sum the window length at each r. The same skeleton gives "number of substrings with at most K distinct characters" and "count subarrays with at most K odd numbers".

Reference solution (Python)

def count_distinct_substrings(s):
    last = {}
    l = ans = 0
    for r, c in enumerate(s):
        if c in last and last[c] >= l:
            l = last[c] + 1
        last[c] = r
        ans += r - l + 1
    return ans

Test cases

Input	Expected
"abc"	6
"aab"	4
"abab"	7
"aaaa"	4