Count Unique Characters of All Substrings of a Given String - Video Solutions

Problem Overview: Given a string s, compute the sum of counts of unique characters for every possible substring. A character contributes to a substring only if it appears exactly once in that substring. The challenge is avoiding the naive enumeration of all substrings while correctly counting each character’s contribution.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Generate every substring using two nested loops and compute the number of unique characters in each substring. For each substring, iterate again to count frequencies and check which characters appear exactly once. This approach directly follows the problem definition but performs redundant work because many substrings share overlapping segments. It works for small inputs but quickly becomes impractical as n grows.

Approach 2: Optimized Contribution Technique (O(n) time, O(1) space)

Instead of evaluating substrings individually, calculate how many substrings each character contributes to as a unique character. Track the previous two occurrences of each character. If a character appears at index i, its contribution equals (i - prev) * (next - i), where prev and next represent the nearest identical characters on each side. This counts all substrings where the character is the only occurrence. Iterating through the string once accumulates the total contribution efficiently.

Approach 3: Hash Map for Fast Lookups (O(n) time, O(k) space)

Maintain a hash map that stores the last two positions for each character. While iterating through the string, update contributions based on these positions. Hash lookups make it easy to support larger alphabets beyond uppercase letters. This technique relies on the same contribution principle but uses a dynamic structure rather than fixed arrays. It combines ideas from hash tables and string processing.

Approach 4: Divide and Conquer via Binary Search (O(n log n) time, O(n) space)

Store all indices of each character in sorted lists. For every position, binary search the previous and next occurrences of that character to compute its contribution range. The substring contribution formula remains the same, but binary search replaces direct index tracking. This approach is useful when preprocessing character positions or when extending the logic to multiple queries on the same string.

Recommended for interviews: The contribution-based O(n) solution is the expected answer. It shows you understand how substring ranges work and how to convert a brute force counting problem into a per-character contribution problem. Explaining the brute force first demonstrates baseline reasoning, while the optimized approach highlights strong knowledge of dynamic programming-style state tracking and index arithmetic.