Count Unique Characters of All Substrings of a Given String

hard string math contribution

Problem

Define countUniqueChars(s) as the number of characters appearing exactly once in s. Return the sum of countUniqueChars(t) for every substring t of s.

Inputs = "ABC"

Output10

All 6 substrings contribute, totaling 10 unique-char occurrences.

s (uppercase letters)

def uniqueLetterString(s):
    last = {}; prev = {}
    res = 0
    for i, c in enumerate(s):
        p = prev.get(c, -1)
        l = last.get(c, -1)
        res += (l - p) * (i - l)
        prev[c] = l
        last[c] = i
    n = len(s)
    for c, l in last.items():
        p = prev.get(c, -1)
        res += (l - p) * (n - l)
    return res

function uniqueLetterString(s) {
  const last = new Map(), prev = new Map();
  let res = 0;
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    const p = prev.has(c) ? prev.get(c) : -1;
    const l = last.has(c) ? last.get(c) : -1;
    res += (l - p) * (i - l);
    prev.set(c, l);
    last.set(c, i);
  }
  const n = s.length;
  for (const [c, l] of last) {
    const p = prev.has(c) ? prev.get(c) : -1;
    res += (l - p) * (n - l);
  }
  return res;
}

import java.util.*;
class Solution {
  public int uniqueLetterString(String s) {
    int[] last = new int[26], prev = new int[26];
    Arrays.fill(last, -1); Arrays.fill(prev, -1);
    int res = 0, n = s.length();
    for (int i = 0; i < n; i++) {
      int c = s.charAt(i) - 'A';
      res += (last[c] - prev[c]) * (i - last[c]);
      prev[c] = last[c];
      last[c] = i;
    }
    for (int c = 0; c < 26; c++) {
      res += (last[c] - prev[c]) * (n - last[c]);
    }
    return res;
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int uniqueLetterString(string s) {
        vector<int> last(26, -1), prev(26, -1);
        int res = 0, n = s.size();
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'A';
            res += (last[c] - prev[c]) * (i - last[c]);
            prev[c] = last[c];
            last[c] = i;
        }
        for (int c = 0; c < 26; c++)
            res += (last[c] - prev[c]) * (n - last[c]);
        return res;
    }
};

Explanation

Listing every substring would be far too slow, so we flip the question around and ask: for each single occurrence of a character, in how many substrings is it the only copy of that letter? Summing those contributions gives the answer.

An occurrence at index i is "unique" in a substring as long as that substring does not also include the previous or next occurrence of the same character. Let prev be the position of the previous occurrence and last be where we currently sit. The substring's left edge can start anywhere in (prev, last] and its right edge anywhere in [i, next).

That gives the formula used in the loop: each character's contribution is (last - prev) * (i - last), where i is the next occurrence. We track, per character, its two most recent positions in the maps last and prev, defaulting to -1.

When a character repeats at i, we settle the contribution of its earlier occurrence, then shift prev = last and last = i. A final tail pass settles the last occurrence of every character, treating the string length n as the "next" boundary.

Example: "ABC". Every letter appears once, and adding up each one's reach across all six substrings totals 10.

Time: O(n) Space: O(1)