i solved this as part of my hard-problem practice set. the main thing i wanted to keep from this one is the pattern: identify the state that actually changes, keep the transitions tight, and avoid doing work twice.
my local solution lives in 3-hard/problems/0828-count-unique-characters-of-all-substrings-of-a-given-string in my leetcode repo, and this post keeps the public notes here on the blog without replacing any of the older writeups.
approach
i treated it as a sliding-window and string problem first, then worked backward from the constraints to choose the data structure or recurrence. for hard problems, that usually matters more than trying to force the first idea that comes to mind.
- write down the state that must be preserved between steps
- remove repeated work with caching, ordering, or pruning
- keep edge cases close to the transition logic
complexity notes
the final complexity depends on the chosen pattern, but the goal was to move away from brute force and make each state, edge, or candidate contribute a bounded amount of work.
what i took away
this is the kind of hard problem where the implementation becomes much easier once the invariant is clear. after that, the code is mostly bookkeeping.