C++で特定の文字をすべて削除した後のASCII値の合計を最小化する方法

文字列が与えられたとき、特定の1文字の出現をすべて削除した後の、各文字のASCII値の合計を最小化することを考えます。例として、「hello」という文字列を扱ってみましょう。この文字列のASCII値の合計は (104 + 101 + 108 + 108 + 111) = 532 となります。次に、各文字の出現回数を確認します。

• h は1回出現するため、コストは 1 × 104 = 104
• e は1回出現するため、コストは 1 × 101 = 101
• l は2回出現するため、コストは 2 × 108 = 216
• o は1回出現するため、コストは 1 × 111 = 111

この中で最も多く出現しているのは l です。したがって、l の出現をすべて削除すれば、合計値は最小化されます。つまり、上記のリストから最大のコストを取り除くことと同じです。最終的な結果は 532 − 216 = 316 となります。

アルゴリズムの考え方はシンプルです。まず文字列全体のASCII値の合計を計算します。次に、文字列に含まれる各文字の出現頻度を数え、「出現回数 × ASCII値」が最大となる文字を特定します。その文字を削除した場合の減少量(最大値)を合計から引いたものが、求める結果となります。

この手法の計算量は、文字列を一度走査して頻度を集計する部分が O(n)、26種類の英小文字を確認する部分が O(26) となるため、全体として O(n) の線形時間で処理できます。ただし、サンプルコードでは英小文字のみを想定している点に注意してください。大文字や数字なども扱う場合は、頻度配列のサイズを拡張する必要があります。

サンプルコード

#include <iostream>
using namespace std;
int minASCIISum(string str, int len) {
    int max_val = INT_MIN, sum = 0;
    int frequency[26] = { 0 };
    for (int i = 0; i < len; i++) {
        frequency[str[i] - 'a']++;
        sum += (int)str[i];
    }
    for (int i = 0; i < 26; i++)
    max_val = max(max_val, frequency[i] * (i + 'a'));
    return (sum - max_val);
}
int main() {
    string str = "hello";
    int n = str.length();
    cout << "Minimized Sum: " << minASCIISum(str, n);
}

実行結果

Minimized Sum: 316

このコードでは、まず各文字の頻度を配列に記録しながらASCII値の総和を求め、その後「頻度 × ASCII値」が最大になる文字のコストを計算して総和から差し引いています。hello の場合は l を削除することで 316 という最小値が得られます。