어떤 문자열 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 이하입니다.

입출력 예

입출력 예 설명

입출력 예 #1

• 다음 표는 "baby"의 각 부분문자열과 그 아름다움을 나타낸 것입니다.

• 따라서, 각 부분문자열의 아름다움을 모두 더한 9를 return 해야 합니다.

입출력 예 #2

• "oo"는 모든 글자가 동일하므로, "oo"의 임의의 부분문자열도 모두 동일한 글자를 가지고 있습니다.
• 따라서, "oo"의 임의의 부분문자열의 아름다움은 전부 0이므로, 0을 return 해야 합니다.