Count Unique Characters of All Substrings of a Given String Solution
Count Unique Characters of All Substrings of a Given String solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Unique Characters of All Substrings of a Given String is a hard coding problem on strings, hash table and counting, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For a string t, let countUnique(t) be the number of characters that occur exactly once in t. For "CODE" that is 4; for "KAIRO" it is 5; for "AABB" it is 0.
Given s, return the sum of countUnique(t) over every substring t of s, modulo 10^9 + 7. Substrings at different positions count separately even when identical.
Example 1
Input: s = "ABC"
Output: 10
Explanation: Every one of the six substrings has all-unique characters: 1+1+1+2+2+3 = 10.
Example 2
Input: s = "ABA"
Output: 8
Explanation: The two A's cancel each other out in the substrings that contain both.
Example 3
Input: s = "KAIRO"
Output: 35
Constraints
1 <= s.length <= 100000s consists of uppercase English letters.
Hints for Count Unique Characters of All Substrings of a Given String
Hint 1
Summing over substrings is hopeless directly. Flip it: count the contribution of each occurrence of each character.
Hint 2
An occurrence at index
iis unique in exactly the substrings that contain it but not the previous or next occurrence of the same character.Hint 3
If
prevandnextare those neighbouring positions, the count of such substrings is(i - prev) × (next - i).
How to solve Count Unique Characters of All Substrings of a Given String
Reverse the order of summation. Instead of asking how many unique characters each substring has, ask how many substrings each occurrence is unique in — a quantity that depends only on its two neighbouring occurrences of the same letter.
Approach
- For each letter keep
last— the index of its most recent occurrence — andprev— the one before that, both starting at-1. - At index
iwith letterc, the occurrence atlast[c]is now fully bracketed: it is unique in(last[c] - prev[c]) × (i - last[c])substrings. Add that. - Shift
prev[c] = last[c]andlast[c] = i. - After the sweep, close out every letter's final occurrence using
nas the right bracket.
Why it works
A substring s[l..r] counts the occurrence at p as unique exactly when prev < l <= p and p <= r < next. There are p - prev choices for l and next - p for r, and these ranges are independent — hence the product. Summing over all occurrences of all letters counts each (substring, unique character) pair exactly once.
Complexity
- Time —
O(n) - Space —
O(26)
Pitfalls
- Enumerating substrings is O(n²) at best and cannot pass the stated limit.
- Forgetting the closing loop drops the contribution of every letter's last occurrence.
- The products reach about
n²/4, which overflows 32 bits — accumulate in 64 bits before the modulo.
Reference solution
Python
def uniqueLetterString(s: str) -> int:
MOD = 1000000007
n = len(s)
last = [-1] * 26
prev = [-1] * 26
total = 0
for i, ch in enumerate(s):
c = ord(ch) - 65
total = (total + (i - last[c]) * (last[c] - prev[c])) % MOD
prev[c] = last[c]
last[c] = i
for c in range(26):
total = (total + (n - last[c]) * (last[c] - prev[c])) % MOD
return totalJava
public static int uniqueLetterString(String s) {
final long MOD = 1000000007L;
int n = s.length();
int[] last = new int[26];
int[] prev = new int[26];
Arrays.fill(last, -1);
Arrays.fill(prev, -1);
long total = 0;
for (int i = 0; i < n; i++) {
int c = s.charAt(i) - 'A';
total = (total + (long) (i - last[c]) * (last[c] - prev[c])) % MOD;
prev[c] = last[c];
last[c] = i;
}
for (int c = 0; c < 26; c++) {
total = (total + (long) (n - last[c]) * (last[c] - prev[c])) % MOD;
}
return (int) total;
}C++
int uniqueLetterString(string s) {
const long long MOD = 1000000007LL;
int n = (int) s.size();
vector<int> last(26, -1), prev(26, -1);
long long total = 0;
for (int i = 0; i < n; i++) {
int c = s[i] - 'A';
total = (total + (long long) (i - last[c]) * (last[c] - prev[c])) % MOD;
prev[c] = last[c];
last[c] = i;
}
for (int c = 0; c < 26; c++) {
total = (total + (long long) (n - last[c]) * (last[c] - prev[c])) % MOD;
}
return (int) total;
}JavaScript
var uniqueLetterString = function(s) {
var MOD = 1000000007;
var n = s.length;
var last = [], prev = [];
for (var t = 0; t < 26; t++) { last.push(-1); prev.push(-1); }
var total = 0;
for (var i = 0; i < n; i++) {
var c = s.charCodeAt(i) - 65;
total = (total + (i - last[c]) * (last[c] - prev[c])) % MOD;
prev[c] = last[c];
last[c] = i;
}
for (var d = 0; d < 26; d++) {
total = (total + (n - last[d]) * (last[d] - prev[d])) % MOD;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets