Leetcode Problem 828. Count Unique Characters of All Substrings of a Given String

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

Leetcode Solutions

Counting Unique Characters in Substrings Using Last Occurrence Indices

  1. Initialize an array index to store the last two occurrence indices for every character in the alphabet.
  2. Initialize res to store the result, which will be the sum of contributions of all characters.
  3. Loop through the string S, and for each character c at index i, update its last two occurrence indices in index.
  4. Calculate the contribution of c using the formula (i - index[c][1]) * (index[c][1] - index[c][0]) and add it to res.
  5. After the loop, go through the index array to add the contributions of characters from their last occurrence to the end of the string.
  6. Return the result res.
UML Thumbnail

Brute Force Approach to Count Unique Characters in Substrings

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...