Count Unique Characters of All Substrings of a Given String - Solution & Explanation
Problem Statement
Let's define a function countUniqueChars(s) that returns the number of unique characters in s.
- For example, calling
countUniqueChars(s)ifs = "LEETCODE"then"L","T","C","O","D"are the unique characters since they appear only once ins, thereforecountUniqueChars(s) = 5.
Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.
Notice that some substrings can be repeated so in this case you have to count the repeated ones too.
Example 1:
Input: s = "ABC" Output: 10 Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC". Every substring is composed with only unique letters. Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
Example 2:
Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.
Example 3:
Input: s = "LEETCODE" Output: 92
Constraints:
1 <= s.length <= 105sconsists of uppercase English letters only.
Approach Overview
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.
Approach 1: Brute Force Approach
This approach involves generating all possible substrings of the given string and calculating the number of unique characters for each substring. While this approach is simple, it is not efficient due to its O(n^3) complexity and is suitable only for small input sizes.
This Python function iterates over all possible substrings of the string s using two nested loops. For each substring, it calculates the number of unique characters using a set and accumulates the result.
Code
Python
Complexity
The time complexity is O(n^3) because we explore all substrings (O(n^2)) and count unique characters (O(n)) for each. The space complexity is O(n) due to the set data structure.
Approach 2: Optimized Approach
This approach improves efficiency by keeping track of character positions as we iterate through the string, reducing the need to generate repetitive substrings. It utilizes two arrays to remember the last two positions of each character, to calculate their contribution effectively in linear time.
This optimized Python function tracks the last two occurrences of each character in the string, updating a result variable in linear time. This avoids recomputing substrings and efficiently calculates the unique contribution of each character to all possible substrings.
Code
Python
Complexity
The time complexity is O(n) since each character is processed a constant number of times. The space complexity is O(1) since we only store a fixed number of characters (26 for uppercase English letters).
Approach 3: Hash Map for Fast Lookups
This approach leverages a hash map to store the given data for constant-time average lookups. The idea is to map each unique element to its index and then use this map to quickly find relevant information when needed. This method allows us to efficiently locate elements and prevents duplicated work when searching for data. It's a commonly used technique when you need fast data retrieval.
The C solution uses a simple linked-list hash map to store key-value pairs. A key is hashed to determine the index in the array, and linked lists are used to handle collisions. We implemented basic insertion and search operations on this map.
Complexity
Time Complexity: O(1) on average for insert and search operations.
Space Complexity: O(n), where n is the number of elements to store.
Approach 4: Divide and Conquer via Binary Search
This approach uses the strategy of divide-and-conquer through binary search to efficiently locate elements in a sorted structure. By splitting the search range in half with each step, the time complexity is significantly reduced compared to linear search. This technique is ideal for searching efficiently in data that can be sorted beforehand.
This C solution implements a binary search algorithm, iteratively halving the search range until the target is found or the range is exhausted, making it very efficient for sorted arrays.
Complexity
Time Complexity: O(log n) for binary search operation.
Space Complexity: O(1), as there is no extra space used beyond input storage.
Approach 5: Calculate the Contribution of Each Character
For each character c_i in the string s, when it appears only once in a substring, it contributes to the count of unique characters in that substring.
Therefore, we only need to calculate for each character c_i, how many substrings contain this character only once.
We use a hash table or an array d of length 26, to store the positions of each character in s in order of index.
For each character c_i, we iterate through each position p in d[c_i], find the adjacent positions l on the left and r on the right, then the number of substrings that meet the requirements by expanding from position p to both sides is (p - l) times (r - p). We perform this operation for each character, add up the contributions of all characters, and get the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n^3) because we explore all substrings (O(n^2)) and count unique characters (O(n)) for each. The space complexity is O(n) due to the set data structure. |
| Optimized Approach | The time complexity is O(n) since each character is processed a constant number of times. The space complexity is O(1) since we only store a fixed number of characters (26 for uppercase English letters). |
| Hash Map for Fast Lookups | Time Complexity: O(1) on average for insert and search operations. |
| Divide and Conquer via Binary Search | Time Complexity: O(log n) for binary search operation. |
| Calculate the Contribution of Each Character | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Conceptual baseline or very small strings |
| Optimized Contribution Technique | O(n) | O(1) | Best general solution for interviews and large inputs |
| Hash Map for Fast Lookups | O(n) | O(k) | When alphabet size varies or characters extend beyond fixed arrays |
| Divide and Conquer with Binary Search | O(n log n) | O(n) | Useful when character positions are pre-indexed or reused across queries |
Video Solution
Count Unique Characters of All Substrings of a Given String | Leetcode 828 • Techdose • 19,247 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Unique Characters of All Substrings of a Given String easy or hard?
Count Unique Characters of All Substrings of a Given String Python/Java solution
How to solve Count Unique Characters of All Substrings of a Given String in O(n)?
What is the best approach for Count Unique Characters of All Substrings of a Given String?
Is Count Unique Characters of All Substrings of a Given String asked at Google/Amazon/Meta?
What data structure is used in Count Unique Characters of All Substrings of a Given String?
What is the time complexity of Count Unique Characters of All Substrings of a Given String?
Ready to solve this problem?
Practice Count Unique Characters of All Substrings of a Given String with our built-in code editor and test cases.
Practice on FleetCode