Count Unique Characters of All Substrings looks brutal — there are O(n²) substrings, and scoring each one seems unavoidable. The trick is to flip the question around and count contributions instead of substrings.
Problem. A character is unique in a string if it appears exactly once. For a string s, define
countUniqueChars(t) as the number of unique characters in t. Return the sum of
countUniqueChars(t) over every substring t of s.
Example: s = "ABA" → answer 8. The substrings and their unique-char counts add up to 8.
The slow way first
The literal approach: generate all O(n²) substrings, and for each one count its unique characters. That is O(n²) substrings times O(n) to scan each — O(n³), hopeless for long strings.
The better question: instead of asking how many unique chars each substring has, ask how many substrings each character is unique in. Both sums are equal — every (substring, unique-char) pair is counted once either way — but the second one we can compute fast.
The idea: count each character's contribution
Take one character at index i. It is the only copy of its letter in a substring exactly when the substring includes i but excludes every other occurrence of that letter. So look at its previous same-letter index prev and its next same-letter index nxt.
The substring may start anywhere in (prev, i] — that is i - prev choices — and end anywhere in [i, nxt) — that is nxt - i choices. So this character is unique in (i - prev) * (nxt - i) substrings. Add that up over every index.
Missing neighbors are handled by the boundaries: if there is no previous copy, prev = -1; if there is no next copy, nxt = len(s).
Walk through it
Step through the animation on "ABA". The pointer i visits each index. For the first A, prev is -1 and next is 2, giving 1 * 2 = 2. For B, which is alone, prev is -1 and next is 3, giving 2 * 2 = 4. For the last A, prev is 0 and next is 3, giving 2 * 1 = 2. Total: 2 + 4 + 2 = 8.
Pseudocode
total = 0
for each index i with character ch in s:
prev = index of the previous ch before i (-1 if none)
nxt = index of the next ch after i (len(s) if none)
total += (i - prev) * (nxt - i) # substrings where ch is unique
return totalThe Python solution
def unique_letter_string(s):
total = 0
for i, ch in enumerate(s):
prev = s.rfind(ch, 0, i)
nxt = s.find(ch, i + 1)
if nxt == -1:
nxt = len(s)
total += (i - prev) * (nxt - i)
return totaltotalaccumulates the contribution of every character.s.rfind(ch, 0, i)finds the last occurrence ofchstrictly beforei, and returns-1if there is none — exactly theprev = -1boundary we want.s.find(ch, i + 1)finds the next occurrence afteri; if it returns-1we treat the boundary aslen(s).(i - prev) * (nxt - i)counts start choices times end choices — the substrings in which this character is the only copy of its letter.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (score every substring) | O(n³) (moderate) | n² substrings, O(n) each |
| Contribution counting (this code) | O(n²) (slow) | rfind/find scan per index |
| With last-two-index maps | O(n) (moderate) | O(1) prev/next lookups |
O(1) (fast)The shown code uses rfind/find, which scan, so it is O(n²) — already a huge win over O(n³). Precomputing each letter's last two seen indices makes prev/next O(1), giving a clean O(n) pass with O(1) extra space (26 letters).
When this pattern shows up
When a problem sums some quantity over all substrings or subarrays, do not enumerate them. Instead
pick one element and count how many of those substrings it contributes to — usually left_count * right_count using its nearest qualifying neighbors on each side. The same move powers sum-of-subarray-
minimums and sum-of-subarray-ranges.
Get the boundaries right: a missing previous copy is prev = -1 (not 0), and a missing next copy is
nxt = len(s) (not len(s) - 1). Off-by-one here silently undercounts the first and last occurrences.
Practice
In s = 'ABA', for the B at index 1, what are its prev and next same-letter indices, and what does it contribute?
1. Why does counting per-character contributions equal summing unique chars over all substrings?
2. For a character at index i with previous same-letter index prev and next nxt, how many substrings is it unique in?
3. If a character has no previous occurrence, what value should prev take?
4. What makes the O(n) version faster than the O(n²) rfind/find version?