题目描述:
LeetCode 828. Unique Letter String
A character is unique in string S
if it occurs exactly once in it.
For example, in string S = "LETTER"
, the only unique characters are "L"
and "R"
.
Let's define UNIQ(S)
as the number of unique characters in string S
.
For example, UNIQ("LETTER") = 2
.
Given a string S, calculate the sum of UNIQ(substring)
over all non-empty substrings of S
.
If there are two or more equal substrings at different positions in S
, we consider them different.
Since the answer can be very large, retrun the answer modulo 10 ^ 9 + 7
.
Example 1:
Input: "ABC" Output: 10 Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC". Evey substring is composed with only unique letters. Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
Example 2:
Input: "ABA" Output: 8 Explanation: The same as example 1, except uni("ABA") = 1.
Note: 0 <= S.length <= 10000
.
题目大意:
给定字符串S,求其各子串中包含的不重复字母的个数。
解题思路:
字符统计
分别统计每个字母出现的下标 假设字母letter的下标数组为idx,将-1和len(S)插入idx的头部和尾部 则sum((idx[i] - idx[i - 1]) * (idx[i + 1] - idx[i]))为letter出现的总次数
Python代码:
class Solution(object):
def uniqueLetterString(self, S):
"""
:type S: str
:rtype: int
"""
letterIdx = collections.defaultdict(list)
for i, c in enumerate(S): letterIdx[c].append(i)
ans = 0
for letter, idx in letterIdx.items():
idx = [-1] + idx + [len(S)]
for x in range(1, len(idx) - 1):
ans += (idx[x] - idx[x - 1]) * (idx[x + 1] - idx[x])
return ans
朴素解法(Time Limit Exceeded)
Python代码:
class Solution(object):
def uniqueLetterString(self, S):
"""
:type S: str
:rtype: int
"""
q = [(set([c]), set([c]), i) for i, c in enumerate(S)]
ans = len(S)
while q:
q0 = []
for c, p, i in q:
if i + 1 == len(S):
continue
if S[i + 1] not in c and S[i + 1] not in p:
c.add(S[i + 1])
elif S[i + 1] in c:
c.remove(S[i + 1])
p.add(S[i + 1])
q0.append((c, p, i + 1))
ans += len(q0[-1][0])
q = q0
return ans
本文链接:http://bookshadow.com/weblog/2018/05/06/leetcode-unique-letter-string/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。