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

Problem link : https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/submissions/

Count Unique Characters of All Substrings of a Given String - LeetCode

 

I don't think this problem is good. Because this problem is not related to data structure and algorithm.

 

The key idea to solve this problem is simple.

 

 

At first, I think the best easy way we can come up with first is that make so every substring and count unique characters in each substrings and then add all.

 

But this way will fail. The maximum lenght of 's' is 10^5. The time complexity of the above way is O(N^2).

 

 

If a one charactor is repeated, it is not important that the charactor is used twice or more.

 

So we can forcus the near same charactors of each charactors.

And the charactor of alphabet is fixed to 26.

 

Let's see below example.

 

s : AAABAAA

 

I will count the cases involving 'B'.

AAAB
AAABA
AAABAA
AAABAAA
AAB
AABA
AABAA
AABAAA
AB
ABA
ABAA
ABAAA
B
BA
BAA
BAAA

 

the number of cases is 16.

 

At leftside of 'B', the number of the cases is 4.

 

AAA

AA

A

(empty)

 

At rightside of 'B', the number of the cases is 4.

 

AAA

AA

A

(empty)

 

So we can get the sum of count of substrings involving 'B'.

4 * 4

(3 - (-1)) * (7 - 3)

((the index of 'B') - (the last index of alphabet B)) * ((the length of string) - (the index of 'B'))

 

 

 

 

Python3

 

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        
        result = 0
        
        chars = [[-1] for x in range(26)]
        
        for i, c in enumerate(s):
            
            chars[ord(c) - ord('A')].append(i)
        
        for lst in chars:
            if len(lst) == 1:
                lst.clear()
            else:
                lst.append(len(s))
        
        for lst in chars:
            if len(lst) == 0:
                continue
            
            for i in range(1, len(lst) - 1):
                result += (lst[i] - lst[i - 1]) * (lst[i + 1] - lst[i])
        return result

 

 

 

If you have any question, please leave a comment.