LeetCode-Solutions/Python/unique-letter-string.py at master · pythonpeixun/LeetCode-Solutions · GitHub

24 lines (20 loc) · 522 Bytes

# Time: O(n)

# Space: O(1)

import string

class Solution(object):

def uniqueLetterString(self, S):

"""

:type S: str

:rtype: int

"""

M = 10**9 + 7

index = {c: [-1, -1] for c in string.ascii_uppercase}

result = 0

for i, c in enumerate(S):

k, j = index[c]

result += (i-j) * (j-k)

index[c] = [j, i]

for c in index:

k, j = index[c]

result += (len(S)-j) * (j-k)

return result % M

Expand file tree