C++で文字列のすべての部分文字列における一意な文字数の総和を計算する方法

まず、countUniqueChars(s) という関数を定義することを考えます。この関数は、文字列 s の中で一度だけ出現する文字(一意な文字)の個数を返します。たとえば s = "HELLOWORLD" の場合、「H」「E」「W」「R」「D」はそれぞれ1回しか現れないため、countUniqueChars(s) = 5 となります。

本問題では、文字列 s が与えられたとき、そのすべての部分文字列 t に対する countUniqueChars(t) の総和を求めます。同じ部分文字列が複数回現れる場合でも、それぞれ別々にカウントする点に注意してください。

答えは非常に大きな値になる可能性があるため、10^9+7 を法とした剰余として返します。

たとえば、入力が "HELLOWORLD" のとき、出力は 128 になります。

解法のアプローチ

各文字について、その出現位置をあらかじめ記録しておくのがポイントです。ある文字が位置 p に出現するとき、直前の出現位置を prev、直後の出現位置を next とすると、この出現が「一意な文字」として数えられる部分文字列の個数は (p − prev) × (next − p) で計算できます。これをすべての出現位置について足し合わせることで、全体の総和を効率よく求めることができます。

具体的な手順

• 関数 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 から開始し、i < n の間、i を1ずつ増やしながら繰り返します。
• x := s[i]
• cnt[x - 'A'] のサイズが 0 の場合、cnt[x - 'A'] の末尾に -1 を挿入します(番兵として機能します)。
• cnt[x - 'A'] の末尾に i を挿入します。
• i := 0 から開始し、i < 26 の間、i を1ずつ増やしながら繰り返します。
• cnt[i] のサイズが 0 の場合は何もせず、次の反復へスキップします。
• cnt[i] の末尾に n を挿入します。
• j := 1 から開始し、j < cnt[i] のサイズ - 1 の間、j を1ずつ増やしながら繰り返します。
• temp := mul(cnt[i][j] - cnt[i][j-1], cnt[i][j+1] - cnt[i][j])
• ans := add(ans, temp)
• 最後に ans を返します。

理解を深めるために、以下の実装例をご覧ください。

実装例(C++)

#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"

出力

128