Count Sum of unique characters in all possible substrings of a string

count_unique_chars_in_all_substrings.py

# Given a string s, count the total number of all unique characters in all the substrings of s
#e.g. ABCA => A[1] + B[1] + C[1] + A[1] + AB[2] + BC[2] + CA[2] + ABC[3] + BCA[3] + ABCA[3]) = 19

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        total_count = 0
        
        dp = defaultdict(int)
        char_last_seen = dict() # If not seen -> 0
        
        
        for i, char in enumerate(s):
            dp[i] = dp[i-1] + (i+1)
            
            if char in char_last_seen:
                # Subtract all strings from start till that char's last occurance
                dp[i] -= (char_last_seen[char] +1)
            
            total_count += dp[i]
            char_last_seen[char] = i
        
        print(dp)
        return total_count

if __name__ == "__main__":
  assert Solution().uniqueLetterString("ABCA") == 19