Scale Engineer

Count Unique Characters of All Substrings of a Given String

Hard
#0782Time: O(N^2), where N is the length of the string. We have two nested loops, each potentially running up to N times. The operations inside the inner loop are constant time.Space: O(1), as we only use a fixed-size array (size 26) for the frequency map, which does not depend on the input string's length.
Patterns
Dynamic Programming
Data structures
Hash TableString

Prompt

Let's define a function countUniqueChars(s) that returns the number of unique characters in s.

  • For example, calling countUniqueChars(s) if s = "LEETCODE" then "L", "T", "C", "O", "D" are the unique characters since they appear only once in s, therefore countUniqueChars(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:

countUniqueChars

Example 3:

Input: s = "LEETCODE"
Output: 92

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of uppercase English letters only.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly follows the problem statement by iterating through all possible substrings of the input string s. For each substring, it calculates the number of unique characters and adds this count to a running total. While straightforward, its performance is poor due to the large number of substrings.

Algorithm

  • Initialize a variable totalSum to 0.
  • Use a nested loop to generate all substrings. The outer loop i from 0 to n-1 defines the start of the substring.
  • The inner loop j from i to n-1 defines the end of the substring.
  • For each substring s.substring(i, j + 1), we need to count its unique characters.
  • To do this efficiently within the loops, we can maintain a frequency map (an array of size 26) for the substring starting at i.
  • As j increases, we update the frequency of the new character s.charAt(j).
  • We also maintain a count of unique characters for the current substring s.substring(i, j + 1). If a character's frequency becomes 1, we increment the unique count. If it becomes 2, we decrement it.
  • Add this unique count to totalSum.
  • After iterating through all substrings, totalSum will hold the final answer.

Walkthrough

The algorithm generates every substring by using two nested loops. The outer loop fixes the starting point i of the substring, and the inner loop iterates from i to the end of the string, defining the endpoint j. For each starting point i, we can efficiently calculate the unique characters for all substrings starting at i by extending the substring one character at a time. We use a frequency array to keep track of character counts for the current substring s[i...j]. As we extend the substring to s[i...j+1], we update the frequency of the new character and adjust the unique character count accordingly. This count is then added to our overall sum.

class Solution {    public int uniqueLetterString(String s) {        int n = s.length();        int totalSum = 0;        for (int i = 0; i < n; i++) {            int[] freq = new int[26];            int uniqueCount = 0;            for (int j = i; j < n; j++) {                int charIndex = s.charAt(j) - 'A';                freq[charIndex]++;                if (freq[charIndex] == 1) {                    uniqueCount++;                } else if (freq[charIndex] == 2) {                    uniqueCount--;                }                totalSum += uniqueCount;            }        }        return totalSum;    }}

Complexity

Time

O(N^2), where N is the length of the string. We have two nested loops, each potentially running up to N times. The operations inside the inner loop are constant time.

Space

O(1), as we only use a fixed-size array (size 26) for the frequency map, which does not depend on the input string's length.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space.

Cons

  • Highly inefficient and will result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints (N up to 10^5).

Solutions

class Solution {public  int uniqueLetterString(String s) {    List<Integer>[] d = new List[26];    Arrays.setAll(d, k->new ArrayList<>());    for (int i = 0; i < 26; ++i) {      d[i].add(-1);    }    for (int i = 0; i < s.length(); ++i) {      d[s.charAt(i) - 'A'].add(i);    }    int ans = 0;    for (var v : d) {      v.add(s.length());      for (int i = 1; i < v.size() - 1; ++i) {        ans += (v.get(i) - v.get(i - 1)) * (v.get(i + 1) - v.get(i));      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem