Count Unique Characters of All Substrings of a Given String
Count Unique Characters of All Substrings of a Given String is a hard arrays & hashing problem solved with the contribution technique pattern.
The best approach, optimal (contribution of each position), runs in O(n) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (count each substring) up.
Problem
For a string t, let countUnique(t) be the number of characters that occur exactly once in t. For example, in "ZOOM" only Z and M appear once, so countUnique("ZOOM") = 2.
You are given a string s of uppercase letters. Return the sum of countUnique(t) over every non-empty substring t of s. Substrings that look the same but start at different positions are counted separately.
Examples
Example 1
- Input
s = "ABA"- Output
8- Why
- "A", "B", "A" give 1 each, "AB" and "BA" give 2 each, and in "ABA" only B appears once, giving 1: 3 + 4 + 1 = 8.
Example 2
- Input
s = "ZZ"- Output
2- Why
- Each "Z" alone gives 1; in "ZZ" the letter repeats, so it gives 0.
Example 3
- Input
s = "ABC"- Output
10- Why
- Three substrings of length 1 give 1 each, two of length 2 give 2 each and "ABC" gives 3.
Constraints
1 <= s.length <= 10^5sconsists of uppercase English letters only.- The answer fits in a 32-bit signed integer.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (count each substring) | O(n³) | O(1) |
| Better (extend each start with a running count) | O(n²) | O(1) |
| Optimal (contribution of each position) | O(n) | O(1) |
1Brute force (count each substring)
O(n³)O(n²) substrings, each counted in O(n).O(1)One array of 26 counts.Enumerate every substring and count, with a 26-entry frequency array, how many letters occur exactly once in it. Add that number to the total.
- For each i, for each j >= i: fill freq from s[i..j].
- Add the number of letters with freq == 1.
class Solution {
public int uniqueLetterString(String s) {
int n = s.length();
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int[] freq = new int[26];
for (int k = i; k <= j; k++) freq[s.charAt(k) - 'A']++;
for (int f : freq) if (f == 1) total++;
}
}
return total;
}
}class Solution:
def uniqueLetterString(self, s: str) -> int:
n = len(s)
total = 0
for i in range(n):
for j in range(i, n):
freq = [0] * 26
for k in range(i, j + 1):
freq[ord(s[k]) - ord('A')] += 1
total += sum(1 for f in freq if f == 1)
return totalclass Solution {
public:
int uniqueLetterString(string s) {
int n = s.size();
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int freq[26] = {0};
for (int k = i; k <= j; k++) freq[s[k] - 'A']++;
for (int f : freq) if (f == 1) total++;
}
}
return total;
}
};function uniqueLetterString(s) {
const n = s.length;
let total = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
const freq = new Array(26).fill(0);
for (let k = i; k <= j; k++) freq[s.charCodeAt(k) - 65]++;
for (const f of freq) if (f === 1) total++;
}
}
return total;
}2Better (extend each start with a running count)
O(n²)Every substring is reached in O(1) from the previous one.O(1)One array of 26 counts.Fix the start i and grow the end j one letter at a time. Keep the frequency array and the number of letters seen exactly once: when a letter's count goes 0 → 1 the number rises, 1 → 2 it falls. Add the current number after every step.
- For each i: freq = zeros, unique = 0.
- For each j from i: c = s[j]; freq[c]++; if freq[c] == 1 then unique++ else if freq[c] == 2 then unique--.
- Add unique to the total.
class Solution {
public int uniqueLetterString(String s) {
int n = s.length();
int total = 0;
for (int i = 0; i < n; i++) {
int[] freq = new int[26];
int unique = 0;
for (int j = i; j < n; j++) {
int c = s.charAt(j) - 'A';
freq[c]++;
if (freq[c] == 1) unique++;
else if (freq[c] == 2) unique--;
total += unique;
}
}
return total;
}
}class Solution:
def uniqueLetterString(self, s: str) -> int:
n = len(s)
total = 0
for i in range(n):
freq = [0] * 26
unique = 0
for j in range(i, n):
c = ord(s[j]) - ord('A')
freq[c] += 1
if freq[c] == 1:
unique += 1
elif freq[c] == 2:
unique -= 1
total += unique
return totalclass Solution {
public:
int uniqueLetterString(string s) {
int n = s.size();
int total = 0;
for (int i = 0; i < n; i++) {
int freq[26] = {0};
int unique = 0;
for (int j = i; j < n; j++) {
int c = s[j] - 'A';
freq[c]++;
if (freq[c] == 1) unique++;
else if (freq[c] == 2) unique--;
total += unique;
}
}
return total;
}
};function uniqueLetterString(s) {
const n = s.length;
let total = 0;
for (let i = 0; i < n; i++) {
const freq = new Array(26).fill(0);
let unique = 0;
for (let j = i; j < n; j++) {
const c = s.charCodeAt(j) - 65;
freq[c]++;
if (freq[c] === 1) unique++;
else if (freq[c] === 2) unique--;
total += unique;
}
}
return total;
}3Optimal (contribution of each position)
O(n)One pass over the string plus a final pass over 26 letters.O(1)Two arrays of 26 positions.Count from the letters' side. Position i adds 1 to every substring in which s[i] is the only copy of its letter. Such a substring must start after prev, the previous index of the same letter, and end before next, the following one. That gives (i - prev) · (next - i) substrings. Walking left to right and remembering the last two positions of each letter, every contribution can be added when the next copy appears (or at the end).
- For each letter keep last[c] and secondLast[c], both starting at -1.
- For each index i with letter c: the previous copy p = last[c] now knows its next copy is i, so add (p - secondLast[c]) · (i - p) when p >= 0. Then secondLast[c] = p, last[c] = i.
- After the scan, for each letter with last[c] = p >= 0, add (p - secondLast[c]) · (n - p).
class Solution {
public int uniqueLetterString(String s) {
int n = s.length();
int[] last = new int[26], secondLast = new int[26];
Arrays.fill(last, -1);
Arrays.fill(secondLast, -1);
long total = 0;
for (int i = 0; i < n; i++) {
int c = s.charAt(i) - 'A';
int p = last[c];
if (p >= 0) total += (long) (p - secondLast[c]) * (i - p);
secondLast[c] = p;
last[c] = i;
}
for (int c = 0; c < 26; c++) {
int p = last[c];
if (p >= 0) total += (long) (p - secondLast[c]) * (n - p);
}
return (int) total;
}
}class Solution:
def uniqueLetterString(self, s: str) -> int:
n = len(s)
last = [-1] * 26
second_last = [-1] * 26
total = 0
for i, ch in enumerate(s):
c = ord(ch) - ord('A')
p = last[c]
if p >= 0:
total += (p - second_last[c]) * (i - p)
second_last[c] = p
last[c] = i
for c in range(26):
p = last[c]
if p >= 0:
total += (p - second_last[c]) * (n - p)
return totalclass Solution {
public:
int uniqueLetterString(string s) {
int n = s.size();
vector<int> last(26, -1), secondLast(26, -1);
long long total = 0;
for (int i = 0; i < n; i++) {
int c = s[i] - 'A';
int p = last[c];
if (p >= 0) total += (long long) (p - secondLast[c]) * (i - p);
secondLast[c] = p;
last[c] = i;
}
for (int c = 0; c < 26; c++) {
int p = last[c];
if (p >= 0) total += (long long) (p - secondLast[c]) * (n - p);
}
return (int) total;
}
};function uniqueLetterString(s) {
const n = s.length;
const last = new Array(26).fill(-1);
const secondLast = new Array(26).fill(-1);
let total = 0;
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i) - 65;
const p = last[c];
if (p >= 0) total += (p - secondLast[c]) * (i - p);
secondLast[c] = p;
last[c] = i;
}
for (let c = 0; c < 26; c++) {
const p = last[c];
if (p >= 0) total += (p - secondLast[c]) * (n - p);
}
return total;
}Edge cases to test
- A single character: the answer is 1
- All characters the same: only the length-1 substrings count, so the answer is
n - All characters different: every substring counts its full length
- Repeated substrings at different positions are counted separately
Hints
Hint 1
Instead of asking how many unique letters each substring has, turn it around: for each position i, in how many substrings is s[i] the only copy of its letter?
Hint 2
s[i] is unique in a substring exactly when the substring starts after the previous occurrence of the same letter and ends before the next one.
Hint 3
If prev and next are those neighbouring positions (use -1 and n when missing), position i contributes (i - prev) · (next - i).
FAQ
What is the best time complexity for Count Unique Characters of All Substrings of a Given String?
Optimal (contribution of each position) runs in O(n) time and O(1) extra space. One pass over the string plus a final pass over 26 letters.
Which pattern does Count Unique Characters of All Substrings of a Given String use?
It is a arrays & hashing problem that uses the contribution technique pattern. Other problems with the same pattern: Count Binary Substrings.
Is there a brute force solution for Count Unique Characters of All Substrings of a Given String?
Yes. Brute force (count each substring) takes O(n³) time and O(1) space. Enumerate every substring and count, with a 26-entry frequency array, how many letters occur exactly once in it.
Which edge cases should I test for Count Unique Characters of All Substrings of a Given String?
A single character: the answer is 1; All characters the same: only the length-1 substrings count, so the answer is n; All characters different: every substring counts its full length; Repeated substrings at different positions are counted separately.