LeetCode 828. Count Unique Characters of All Substrings of a Given String
忘記在哪看到人家說是2262. total appeal of a string的相似題,但至少和我的解法不同,不是很確定相似在哪裡。
題目Permalink
定義函數countUniqueChars(s),會回傳s中有幾個只出現一次的字元。例如countUniqueChars(“LEETCODE”),只出現一次的字元有[“L”,”T”,”C”,”O”,”D”],所以回傳5。
輸入字串s,對s的所有子字串傳入countUniqueChars,並回傳加總值。
解法Permalink
我用的是和2104. sum of subarray ranges相同的概念,計算每個位置字元的貢獻值。
與其計算子字串能產生的值,不如計算每個位置的字元能提供多少值。
先遍歷一次s,依字元將索引分類,再對每個分類好的索引計算貢獻值,例:
s=’abacba’
a的索引=[0,2,5]
位於0的a左邊有0個元素,右邊有1個元素可以組成子陣列,共12=2
位於2的a左邊有1個元素,右邊有2個元素可以組成子陣列,共23=6
位於5的a左邊有2個元素,右邊有0個元素可以組成子陣列,共31=3
b的索引=[1,4]
位於1的b左邊有1個元素,右邊有2個元素可以組成子陣列,共23=6
位於4的b左邊有2個元素,右邊有1個元素可以組成子陣列,共32=6
c的索引=[3]
位於3的c左邊有3個元素,右邊有2個元素可以組成子陣列,共43=12
總答案為2+6+3+6+6+12=35
class Solution:
def uniqueLetterString(self, s: str) -> int:
N=len(s)
d=defaultdict(list)
for i,n in enumerate(s):
d[n].append(i)
ans=0
for k in d:
idx=[-1]+d[k]+[N]
for i in range(1,len(idx)-1):
ans+=(idx[i]-idx[i-1])*(idx[i+1]-idx[i])
return ans