Count Unique Characters of All Substrings of a Given String

Hard Arrays & Hashing Contribution Technique Original on LeetCode

Reported atAmazon

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^5
  • s consists 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n³)O(n²) substrings, each counted in O(n).
SpaceO(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.

  1. For each i, for each j >= i: fill freq from s[i..j].
  2. 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;
    }
}

2Better (extend each start with a running count)

TimeO(n²)Every substring is reached in O(1) from the previous one.
SpaceO(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.

  1. For each i: freq = zeros, unique = 0.
  2. For each j from i: c = s[j]; freq[c]++; if freq[c] == 1 then unique++ else if freq[c] == 2 then unique--.
  3. 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;
    }
}

3Optimal (contribution of each position)

TimeO(n)One pass over the string plus a final pass over 26 letters.
SpaceO(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).

  1. For each letter keep last[c] and secondLast[c], both starting at -1.
  2. 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.
  3. 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;
    }
}

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.