Leetcode: 828. Count Unique Characters of All Substrings of a Given String

Mistake: Misread the problem
Mistake: Bug caused by incorrect assumption
Mistake: High constant factor in the implementation
Pattern: Compute value for all subsequences of an array.
Can we reuse or extend a solution from a sub-problem to solve the next sub-problem more efficiently? Let \(f(i)=\sum_{i \leq j < n} countUniqueChars(j)\) the function that we want to compute efficiently. Be \(i\) the first index from the left to right that is duplicated, and \(j\) an index where \(s[i]=s[j]\) and \(i

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        N = len(s)

        nxt = {}
        last = {}
        for c in set(s):
            last[c] = N
            nxt[N, c] = N

        for i in range(N - 1, -1, -1):
            nxt[i, s[i]] = last[s[i]]
            last[s[i]] = i

        ans = 0
        cur = 0
        for i in range(N - 1, -1, -1):
            j = nxt[i, s[i]]
            k = nxt[j, s[i]]
            cur += (j - i) - (k - j)
            ans += cur
        return ans


assert Solution().uniqueLetterString("ABC") == 10
assert Solution().uniqueLetterString("ABA") == 8
assert Solution().uniqueLetterString("LEETCODE") == 92