Count Unique Characters of All Substrings of a Given String

---

Count Unique Characters of All Substrings of a Given String: Let's define a function countUniqueChars(s) that returns the number of unique characters on 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 <= 10^5
• s consists of uppercase English letters only.

---

Try this Problem on your own or check similar problems:

1. Total Appeal of A String

Solution:

Java

public int uniqueLetterString(String s) {
  int totalLength = 0, length = 0;
  int[] lastOccurence = new int[26], addition = new int[26];
  Arrays.fill(lastOccurence, -1);

  for (int i = 0; i < s.length(); ++i) {
    int idx = s.charAt(i) - 'A';
    length -= addition[idx];

    addition[idx] = i - lastOccurence[idx];
    lastOccurence[idx] = i;

    length += addition[idx];
    totalLength += length;
  }

  return totalLength;
}

JavaScript

var uniqueLetterString = function (s) {
  let totalLength = 0;
  let length = 0;
  const lastOccurrence = new Array(26).fill(-1);
  const addition = new Array(26).fill(0);

  for (let i = 0; i < s.length; i++) {
    const idx = s.charCodeAt(i) - 65;
    length -= addition[idx];

    addition[idx] = i - lastOccurrence[idx];
    lastOccurrence[idx] = i;

    length += addition[idx];
    totalLength += length;
  }

  return totalLength;
};

Python

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        totalLength = 0
        length = 0
        lastOccurrence = [-1] * 26
        addition = [0] * 26

        for i in range(len(s)):
            idx = ord(s[i]) - 65
            length -= addition[idx]

            addition[idx] = i - lastOccurrence[idx]
            lastOccurrence[idx] = i

            length += addition[idx]
            totalLength += length

        return totalLength

C++

class Solution {
public:
    int uniqueLetterString(string s) {
        int totalLength = 0;
        int length = 0;
        vector<int> lastOccurrence(26, -1);
        vector<int> addition(26, 0);

        for (int i = 0; i < s.length(); i++) {
            int idx = s[i] - 'A';
            length -= addition[idx];

            addition[idx] = i - lastOccurrence[idx];
            lastOccurrence[idx] = i;

            length += addition[idx];
            totalLength += length;
        }

        return totalLength;
    }
};

---

Time/Space Complexity:

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

---

Explanation:

We have linear time complexity since we iterate over all characters in the string with constant space since by the problem statement, we're only given uppercase English letters. We have two helper arrays, one lastOccurence is tracking the latest occurrence for each letter, and addition so we can track how many new substrings were generated with latest addition of each letter. We also keep two length variables; one is global length for lengths of every substring totalLength and length is tracking the current/local substring length. We iterate over letters of the input string and for each iteration we do the following:

• We first remove the addition we got with latest occurrence of the current letter since letter will now be duplicated and will not add anything to countUniqueChars of each of the substring already containing it.
• When we add the new letter, we calculate additions by checking the current index and index of last occurrence.
• We store the index as the latest occurrence of the current letter.
• We know that the number of new strings that can be generated is equal to the number of letters between the latest occurrence of letter and current letter index, so we always add the current letter additions to the local length.
• Finally, we add the local count to global totalCount which we return as our result.