C++で2つの大文字の間に存在する異なる小文字の最大数を求める方法

この記事では、与えられた文字列の中で、2つの大文字アルファベットに挟まれた区間に存在する「異なる小文字アルファベット」の最大数を求める問題を解説します。

まず、具体的な例を使って、何をする必要があるのかを理解しましょう。

入力

str = “JKyubDoorG”

出力

3

説明

大文字の K と D の間には「yub」が存在し、すべて異なる小文字であるため、カウントは 3 になります。

また、大文字の D と G の間には「oor」が存在しますが、‘o’ が重複しているため、異なる文字として数えると 2 になります。今回は重複しない文字のみを対象としています。

したがって、出力は 3 となります。

入力

str = “ABcefsTaRpaep”

出力

4

プログラムのアプローチ

• 関数 Max() 内で int size = s.length() を初期化し、与えられた文字列の長さを格納します。

• i = 0 から i < size までループし、if (s[i] >= 'A' && s[i] <= 'Z') で最初の大文字を見つけたら i をインクリメントして break します。これにより、文字列の先頭にある小文字（どの大文字にも挟まれていない部分）を無視できます。

• 最終的な答えを格納する int ans = 0 と、各小文字の出現回数を記録する配列 cnt[26] = {0} を初期化します。

• i = 0 から i < size までループし、if (s[i] >= 'A' && s[i] <= 'Z') で現在の文字が大文字かどうかを判定します。大文字の場合は、現在の区間の最大値を保持する int CurrMax = 0 を初期化します。

• 添字 0 から 25 までループし、cnt[i] > 0 であれば CurrMax をインクリメントします。これにより、直前の区間に出現した異なる小文字の総数が得られます。

• 内側の for ループを抜けた後、ans = max(ans, CurrMax) として答えを更新し、memset(cnt, 0, sizeof(cnt)) を使って cnt[] 配列をリセットして次の区間に備えます。

• 上記の if 文を閉じ、if (s[i] >= 'a' && s[i] <= 'z') で現在の文字が小文字かどうかを確認します。小文字の場合は cnt[s[i] - 'a']++ で出現回数をカウントします。

• for ループを閉じ、ans を返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int Max(string s){
    int size = s.length();
    // 先頭の小文字を無視する
    for (int i = 0; i < size; i++){
        if (s[i] >= 'A' && s[i] <= 'Z'){
            i++;
            break;
        }
    }
    int ans = 0;
    int cnt[26] = { 0 };
    for (int i = 0; i < size; i++) {
        // 文字が大文字の場合
        if (s[i] >= 'A' && s[i] <= 'Z'){
            // 区間内に出現したすべての
            // 異なる小文字を数える
            int CurrMax = 0;
            for (int i = 0; i < 26; i++){
                if (cnt[i] > 0)
                    CurrMax++;
            }
            // ans を更新
            ans = max(ans, CurrMax);
            // カウント配列をリセット
            memset(cnt, 0, sizeof(cnt));
        }
        // 文字が小文字の場合
        if (s[i] >= 'a' && s[i] <= 'z')
            cnt[s[i] - 'a']++;
    }
    return ans;
}
// ドライバ関数
int main(){
    string str = "JKyubDoorG";
    cout << Max(str);
    return 0;
}

出力

3