Description

어떤 문자열 x의 "아름다움"을 다음과 같이 정의합니다.

  • 만약 x의 모든 글자가 전부 같다면, 0입니다.
  • 그렇지 않다면, 서로 다른 글자가 위치해 있는 두 인덱스 i, j를 골랐을 때의 j-i 값들 중 최대값입니다.

예를 들어, 문자열 "abbca"의 아름다움은 3입니다. 인덱스 1(b)4(a)를 고르거나, 또는 0(a)3(c)를 고를 때 최대값이기 때문입니다.

영어 소문자로 이루어진 문자열 s가 매개변수로 주어집니다. s의 모든 부분문자열의 아름다움의 합을 return 하도록 solution 함수를 완성해주세요.


제한 사항
  • s의 길이는 1 이상 300,000 이하입니다.

입출력 예
s result
"baby" 9
"oo" 0

입출력 예 설명

입출력 예 #1

  • 다음 표는 "baby"의 각 부분문자열과 그 아름다움을 나타낸 것입니다.
인덱스 범위 부분문자열 아름다움
0 ~ 0 "b" 0
0 ~ 1 "ba" 1 ("b", "a" 선택)
0 ~ 2 "bab" 1 (앞 "b", "a" 선택 또는 "a", 뒤 "b" 선택)
0 ~ 3 "baby" 3 (앞 "b", "y" 선택)
1 ~ 1 "a" 0
1 ~ 2 "ab" 1 ("a", "b" 선택)
1 ~ 3 "aby" 2 ("a", "y" 선택)
2 ~ 2 "b" 0
2 ~ 3 "by" 1 ("b", "y" 선택)
3 ~ 3 "y" 0
  • 따라서, 각 부분문자열의 아름다움을 모두 더한 9를 return 해야 합니다.

입출력 예 #2

  • "oo"는 모든 글자가 동일하므로, "oo"의 임의의 부분문자열도 모두 동일한 글자를 가지고 있습니다.
  • 따라서, "oo"의 임의의 부분문자열의 아름다움은 전부 0이므로, 0을 return 해야 합니다.
Result Stop
Result of [Run] or [Submit] will be displayed here