828. Count Unique Characters of All Substrings of a Given String LeetCode Solution

In this guide, you will get 828. Count Unique Characters of All Substrings of a Given String LeetCode Solution with the best time and space complexity. The solution to Count Unique Characters of All Substrings of a Given String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Count Unique Characters of All Substrings of a Given String solution in C++
4. Count Unique Characters of All Substrings of a Given String solution in Java
5. Count Unique Characters of All Substrings of a Given String solution in Python
6. Additional Resources

Problem Statement of Count Unique Characters of All Substrings of a Given String

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:

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 <= 105
s consists of uppercase English letters only.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(26) = O(1)

828. Count Unique Characters of All Substrings of a Given String LeetCode Solution in C++

class Solution {
 public:
  int uniqueLetterString(string s) {
    int ans = 0;
    // the number of unique letters in all the substrings ending in the index so
    // far
    int dp = 0;
    vector<int> lastCount(26);
    vector<int> lastSeen(26, -1);

    for (int i = 0; i < s.length(); ++i) {
      const int c = s[i] - 'A';
      const int newCount = i - lastSeen[c];
      // Substract the duplicates.
      dp -= lastCount[c];
      // Add count of s[lastSeen[c] + 1..i], s[lastSeen[c] + 2..i], ..., s[i].
      dp += newCount;
      lastCount[c] = newCount;
      lastSeen[c] = i;
      ans += dp;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

828. Count Unique Characters of All Substrings of a Given String LeetCode Solution in Java

class Solution {
  public int uniqueLetterString(String s) {
    int ans = 0;
    // the number of unique letters in all the substrings ending in the index so
    // far
    int dp = 0;
    int[] lastCount = new int[26];
    int[] lastSeen = new int[26];
    Arrays.fill(lastSeen, -1);

    for (int i = 0; i < s.length(); ++i) {
      final int c = s.charAt(i) - 'A';
      final int newCount = i - lastSeen[c];
      // Substract the duplicates.
      dp -= lastCount[c];
      // Add count of s[lastSeen[c] + 1..i], s[lastSeen[c] + 2..i], ..., s[i].
      dp += newCount;
      lastCount[c] = newCount;
      lastSeen[c] = i;
      ans += dp;
    }

    return ans;
  }
}
// code provided by PROGIEZ

828. Count Unique Characters of All Substrings of a Given String LeetCode Solution in Python

class Solution:
  def uniqueLetterString(self, s: str) -> int:
    ans = 0
    # the number of unique letters in all the substrings ending in the index so
    # far
    dp = 0
    lastCount = {}
    lastSeen = {}

    for i, c in enumerate(s):
      newCount = i - lastSeen.get(c, -1)
      # Substract the duplicates.
      dp -= lastCount.get(c, 0)
      # Add count of s[lastSeen[c] + 1..i], s[lastSeen[c] + 2..i], ..., s[i].
      dp += newCount
      lastCount[c] = newCount
      lastSeen[c] = i
      ans += dp

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.