소문자 문자열 s가 있다고 가정하고 s의 모든 하위 문자열에서 고유한 문자 수의 합을 찾아야 합니다. 답이 매우 크면 결과 모드 10^9+7을 반환합니다.
따라서 입력이 s ="xxy"와 같으면 하위 문자열과 해당 개수가 -
이므로 출력은 6이 됩니다.-
"x" :1
-
"x" :1
-
"y" :1
-
"xx" :0("x"는 구별되지 않음)
-
"xy" :2
-
"xxy" :1("x"가 구별되지 않기 때문에)
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=10^9 + 7
-
prev_seen :=새로운 빈 지도
-
답변 :=0
-
util() 함수를 정의합니다. 이것은 i, 기호가 필요합니다.
-
prev_seen[symbol] :=단일 값이 -1인 목록
-
prev :=prev_seen[기호]
-
이전
끝에 i 삽입 -
이전 크기> 2인 경우
-
left :=prev의 첫 번째 요소 및 prev에서 첫 번째 요소 삭제
-
가운데 :=이전[0], 오른쪽 :=이전[1]
-
cnt :=(가운데 - 왼쪽) *(오른쪽 - 가운데)
-
ans :=(ans + cnt) 모드 m
-
-
s의 각 인덱스 i와 값 기호에 대해 수행
-
유틸리티(i, 기호)
-
-
prev_seen의 각 기호에 대해 수행
-
util(s의 크기, 기호)
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution:
def solve(self, s):
m = 10 ** 9 + 7
prev_seen = {}
ans = 0
def util(i, symbol):
nonlocal ans
prev = prev_seen.setdefault(symbol, [−1])
prev.append(i)
if len(prev) > 2:
left = prev.pop(0)
middle, right = prev
cnt = (middle − left) * (right − middle)
ans = (ans + cnt) % m
for i, symbol in enumerate(s):
util(i, symbol)
for symbol in prev_seen:
util(len(s), symbol)
return ans
ob = Solution()
s = "xxy"
print(ob.solve(s)) 입력
xxy
출력
6