Count Unique Characters of All Substrings of a Given String

Count Unique Characters of All Substrings of a Given String

What is this problem about?

The Count Unique Characters of All Substrings of a Given String interview question is a challenging string manipulation problem. You are asked to define a function countUniqueChars(s) that returns the number of characters that appear exactly once in string s. The task is to find the sum of this function's output for every possible substring of a given input string. Because a string of length $n$ has O(n^2) substrings, a brute-force approach is often too slow.

Why is this asked in interviews?

Companies like Microsoft and Amazon use this string coding problem to test a candidate's ability to think beyond brute force. It requires a shift in perspective: instead of iterating over every substring and counting unique characters, you should iterate over each character and determine which substrings it contributes to. This "contribution-based" thinking is a hallmark of senior-level algorithmic problem-solving.

Algorithmic pattern used

The most efficient Dynamic Programming interview pattern or Hash Table approach involves calculating the contribution of each character s[i]. A character s[i] is unique in a substring only if that substring includes s[i] but does not include the previous occurrence of the same character (prev[i]) or the next occurrence (next[i]). The number of such substrings is calculated as (i - prev[i]) * (next[i] - i).

Example explanation

Consider the string "ABC".

• Substrings: "A", "B", "C", "AB", "BC", "ABC".
• Character 'B' at index 1:
  • Previous 'B' is at index -1 (virtual boundary).
  • Next 'B' is at index 3 (virtual boundary).
  • Substrings where 'B' is unique: (1 - (-1)) * (3 - 1) = 2 * 2 = 4.
  • These are "B", "AB", "BC", "ABC". By summing these products for all indices, you get the total unique character count.

Common mistakes candidates make

• Brute Force TLE: Trying to generate all O(n^2) substrings and counting characters, which results in O(n^3) or O(n^2) time complexity.
• Handling Boundaries: Not correctly setting the initial "previous" positions to -1 or the final "next" positions to the string length.
• Integer Overflow: For very long strings, the sum of products can exceed the capacity of a 32-bit integer.

Interview preparation tip

Master the "Contribution Technique." Whenever you are asked to sum a property across all subarrays or substrings, ask yourself: "In how many subarrays does this specific element contribute to the total?" This often reduces an O(n^2) problem to O(n).