[競プロ][Leetcode828] 貢献度を使って数え上げ問題を解く

概要

数え上げ問題を解く方法の１つに貢献度を使う方法がある。
下記の問題を元に解説する
Leetcode 828. Count Unique Characters of All Substrings of a Given String

問題の内容

前提

ある文字列sがある。

s = "LEETCODE"

この文字列sのユニーク数を下記のように定義する。

sの中に含まれている文字の中で１つしか存在しない文字の数

今回の例ではL, T, C, O, Dがそれぞれ１つしか存在しないのでsのユニーク数は5となる。

問題

ある文字列sが与えられたとき、sの部分文字列のユニーク数を全て足した数は何になるか。

例

s = "ABA"のとき、部分文字列は下記が考えられる。部分文字列を()で囲む。

(A)BA
(AB)A
(ABA)
A(B)A
A(BA)
AB(A)

またそれぞれのユニーク数は下記になる。

(A)BA = 1
(AB)A = 2
(ABA) = 1 # Aはユニークでないため数えない
A(B)A = 1
A(BA) = 2
AB(A) = 1

これを全て足すと8になるので、これが答え。

愚直な解法

文字列sの長さをNとすると、作成可能な部分文字列はN^2個作成可能
それぞれの部分文字列に関してユニーク数を計算するのにO(N)かかる。
愚直に計算すると、O(N^3)の計算量が必要。

貢献度を使った解法

ABAの例で考える。
部分文字列を作成して計算するのでなく、それぞれの文字のみに注目する。
まずは一番左にあるAが含まれる部分文字列の中で、答えに含まれるものは下記になる。

(A)BA
(AB)A

(ABA)の文字列は答えに含まれない、なぜならAが重複しているため数えられることはない。
このときの数(上記の場合は2)は一番左のAの貢献度と考えられる。
全ての文字における貢献度を足し合わせることで答えを求めることが可能。
またそれぞれの文字の貢献度は書きで計算が可能

文字の左に配置できる(の数 * 文字の右に配置できる)の数

上記の例では、(は一番左にのみ配置可能。)は次のAの手前まで配置可能
よって一番左の文字列Aの貢献度は1 * 2ということがわかる。

同様にBの貢献度は2 * 2、Cの貢献度は2 * 1、これらを足すと８となる。

実装

int uniqueLetterString(string s) {
    // 各文字の出現場所を配列で持つ
    map<char, vector<int>> mp;
        
    int n = s.size();
    for (int i=0; i<n; i++) {
        char c = s[i];
        mp[c].push_back(i);
    }
        
    int ans = 0;
    for (int i=0; i<n; i++) {
        char c = s[i];
        vector<int>& v = mp[c];
        // 文字の出現場所を特定
        auto it = lower_bound(v.begin(), v.end(), i);

        // 文字の左に配置可能な(の数を計算
        int left = i+1;
        if (it != v.begin()) left = i - *(it-1);

        // 文字の右に配置可能な)の数を計算
        int right = n-i;
        if ((it+1) != v.end()) right = *(it+1) - i;

        ans += left*right;
    }
        
    return ans;
}