Count Unique Characters of All Substrings

January 28, 2024

Problem Statement #

Given a string s, return the sum of the number of unique characters in all substrings of s. In other words, you will be given a string and you need to sum up the total number of unique characters that appear in every possible substring of the string.

Example:

1. Input: s = “ABA” Output: 9 Explanation: The unique characters in all substrings are [“A”,“B”,“A”,“AB”,“BA”,“ABA”], with counts [1,1,1,2,2,2]. The sum is 1+1+1+2+2+2 = 9.

Solution Approach #

The solution uses the concept of contribution of each character to the total count.

Code (Python) #

from collections import Counter

def unique_char_substrings(s):
  """
  Calculates the sum of the number of unique characters in all substrings of a string.

  Args:
      s: The input string.

  Returns:
      The sum of the number of unique characters in all substrings of the string.
  """
  count = 0
  for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
      count += len(Counter(s[i:j]))
  return count

# Example usage
s = "ABA"
unique_chars = unique_char_substrings(s)
print(f"The sum of unique characters in all substrings of '{s}' is: {unique_chars}")