Count Unique Characters Of All Substrings Of A Given String - Leetcode Solution

Problem Statement:

Given a string s, return the sum of all unique characters of all substrings of s.

Example 1:

Input: s = "ABC" Output: 10 Explanation: The substrings with unique characters are "A","B","C","AB","BC" and "ABC". The sum of their lengths is 1 + 1 + 1 + 2 + 2 + 3 = 10.

Example 2:

Input: s = "ABA" Output: 8 Explanation: The substrings with unique characters are "A","B","AB" and "BA". The sum of their lengths is 1 + 1 + 2 + 2 = 8.

Constraints:

1 <= s.length <= 10^5 s consists of lowercase English letters.

Solution:

The given problem can be solved using a brute force approach by generating all the possible substrings of the given string and then counting the unique characters for each of them. However, this approach would take O(n^3) time complexity which is not efficient.

A more efficient approach is to iterate through each character of the string and calculate the contribution of that character in all possible substrings containing it. We can use two arrays to store the last occurrence of each character and the sum of unique characters for each substring ending at the current index.

Let's go through the algorithm step by step:

1. Initialize two arrays last and sum_arr of size 26 (one for each letter of the alphabet) with -1 and 0 respectively. Here last[i] stores the index of the last occurrence of the ith letter in the string and sum_arr[i] stores the sum of unique characters for all possible substrings ending at the current index.

2. Iterate through the string s and for each character do the following: a. If the character has not been encountered before, add its index to the sum of unique characters for all possible substrings ending at the current index. b. If the character has been encountered before, calculate the contribution of that character in all possible substrings containing it. For example, if the character 'a' occurs at index i and has last occurrence at index j, then the contribution of 'a' in all substrings ending at index i is (i-j)*(i-j+1)/2. Add this contribution to the sum of unique characters for all possible substrings ending at the current index.

3. Return the sum of all elements in the sum_arr array.

Let's see the Python code implementation:

class Solution: def uniqueLetterString(self, s: str) -> int: last = [-1] * 26 # stores last occurrence of each character sum_arr = [0] * len(s) # stores sum of unique characters for all possible substrings ending at current index MOD = 10**9 + 7 res = 0

    for i in range(len(s)):
        c = ord(s[i]) - ord('A')
        if last[c] == -1:
            sum_arr[i] = (i+1) * (i+2) // 2
        else:
            prev = last[c]
            sum_arr[i] = (i-prev) * (i-prev+1) // 2 - sum_arr[prev]
        last[c] = i
        res = (res + sum_arr[i]) % MOD
    
    return res

We have used ord(s[i]) - ord('A') to get the index of the current character in the last and sum_arr arrays. We have also used the formula (i-j)*(i-j+1)/2 to calculate the contribution of a character in all possible substrings containing it.

Time Complexity: O(n) Space Complexity: O(n)

The above approach uses dynamic programming to solve the problem in O(n) time complexity and O(n) space complexity.

1