C++でテキストのボリューム（最大大文字数）をカウントする方法

問題概要

n文字の文字列Sがあるとします。Sは、英大文字・小文字で構成された単語が半角スペース1つずつで区切られたテキストです。

ここで、単語のボリュームとは、その単語に含まれる大文字の数を指し、テキストのボリュームとは、テキスト内のすべての単語の中で最も大きいボリュームのことです。この記事では、与えられたテキストのボリュームを求めるC++プログラムを紹介します。

解法のアプローチ

この問題は、文字列を先頭から1文字ずつ走査することで効率的に解けます。基本的な考え方は以下の通りです。

• 現在見ている単語内の大文字の数をカウントする変数を用意する
• スペースに到達した時点で、それまでのカウントと現在の最大値を比較して更新する
• 文字列の末尾まで処理した後も、最後の単語のカウントを忘れずに反映する

アルゴリズムの手順

ans := 0
a := 0
n := size of S
for initialize i := 0, when i <= n, update (increase i by 1), do:
    s := S[i]
    if s >= 'A' and s <= 'Z', then:
        (increase a by 1)
    if s is same as blank space, then:
        ans := maximum of ans and a
        a := 0
ans := maximum of ans and a
return ans

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(string S){
    int ans = 0, a = 0;
    int n = S.size();
    for (int i = 0; i <= n; i++){
        char s = S[i];
        if ((s >= 'A') && (s <= 'Z'))
            a++;
        if (s == ' '){
            ans = max(ans, a);
            a = 0;
        }
    }
    ans = max(ans, a);
    return ans;
}
int main(){
    string S = "Paper MILL";
    cout << solve(S) << endl;
}

コードのポイント

• ループ条件を i <= n としているため、文字列終端のヌル文字 '\0' も走査されます。これにより、最後の単語がスペースで終わらない場合でも、最終的な max(ans, a) の処理と合わせて正しく結果が得られます。
• 時間計算量はO(n)、空間計算量はO(1)と非常に効率的です。

入力例

"Paper MILL"

出力例

4

実行結果の解説

入力文字列 "Paper MILL" の場合、「Paper」には大文字が1個（P）含まれ、「MILL」には大文字が4個（M、I、L、L）含まれています。テキストのボリュームは各単語のボリュームの最大値なので、答えは4となります。