C++에서 문자열의 모든 부분 문자열에 대한 고유 문자 수의 합 구하기

countUniqueChars(s)라는 함수를 정의한다고 가정해 보겠습니다. 이 함수는 문자열 s에서 한 번만 등장하는 고유 문자의 개수를 반환합니다. 예를 들어 s = "HELLOWORLD"인 경우 'H', 'E', 'W', 'R', 'D'는 각각 한 번만 나타나므로 고유 문자에 해당하며, 따라서 countUniqueChars(s) = 5가 됩니다.

이번 문제에서는 주어진 문자열 s에 대해, s의 모든 부분 문자열 t에 대한 countUniqueChars(t) 값의 총합을 구해야 합니다. 동일한 부분 문자열이 여러 번 나타나는 경우에는 중복된 횟수만큼 모두 더해야 합니다.

계산 결과가 매우 커질 수 있으므로, 최종 답은 10^9 + 7로 나눈 나머지를 반환하면 됩니다.

예를 들어 입력이 "HELLOWORLD"라면 출력은 128입니다.

문제 해결 접근 방법

이 문제는 기여도(contribution) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 문자의 등장 위치를 기록한 뒤, 해당 문자가 어떤 부분 문자열에서 고유 문자로 작동하는지 그 경우의 수를 계산하는 것입니다.

특정 위치 j에 있는 문자가 고유 문자가 되려면, 부분 문자열의 시작점은 이전에 같은 문자가 등장한 위치보다 뒤여야 하고, 끝점은 다음에 같은 문자가 등장하는 위치보다 앞이어야 합니다. 따라서 가능한 경우의 수는 두 구간 길이의 곱으로 계산됩니다.

구체적인 해결 단계는 다음과 같습니다.

add() 함수를 정의합니다. 매개변수 a, b를 받아 (a mod m) + (b mod m)을 반환합니다.
mul() 함수를 정의합니다. 매개변수 a, b를 받아 (a mod m) × (b mod m)을 반환합니다.
메인 로직에서 다음을 수행합니다.
- n := 문자열 s의 길이, ans := 0으로 초기화합니다.
- 크기 26의 벡터 배열 cnt를 선언합니다.
- i := 0부터 n 미만까지 반복하며 다음을 수행합니다.
  - x := s[i]
  - cnt[x - 'A']의 크기가 0이라면, 왼쪽 경계값으로 -1을 먼저 삽입합니다.
  - 현재 인덱스 i를 cnt[x - 'A']에 삽입합니다.
- i := 0부터 26 미만까지 반복하며 다음을 수행합니다.
  - cnt[i]의 크기가 0이면 해당 알파벳은 등장하지 않았으므로 건너뜁니다.
  - 배열의 오른쪽 경계값으로 n을 삽입합니다.
  - j := 1부터 cnt[i]의 크기 미만까지 반복하며 다음을 수행합니다.
    - temp := mul(cnt[i][j] - cnt[i][j-1], cnt[i][j+1] - cnt[i][j])
    - ans := add(ans, temp)
ans를 반환합니다.

아래 예시 코드를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
    public:
    lli add(lli a, lli b){
        return (a % m) + (b % m);
    }
    lli mul(lli a, lli b){
        return (a % m) * (b % m);
    }
    int uniqueLetterString(string s) {
        int n = s.size();
        int ans = 0;
        vector<int> cnt[26];
        for (int i = 0; i < n; i++) {
            char x = s[i];
            if (cnt[x - 'A'].size() == 0) {
                cnt[x - 'A'].push_back(-1);
            }
            cnt[x - 'A'].push_back(i);
        }
        for (int i = 0; i < 26; i++) {
            if (cnt[i].size() == 0)
            continue;
            cnt[i].push_back(n);
            for (int j = 1; j < cnt[i].size() - 1; j++) {
                lli temp = mul(cnt[i][j] - cnt[i][j - 1], cnt[i][j +
                1] - cnt[i][j]);
                ans = add(ans, temp);
            }
        }
        return ans;
   }
};
main(){
    Solution ob;
    cout << (ob.uniqueLetterString("HELLOWORLD"));
}

입력

"HELLOWORLD"