C++で最初と最後の要素が同じ部分配列の最大長を求める方法

問題概要

この問題では、文字の配列（文字列）が与えられます。私たちの課題は、最初と最後の要素が同じである部分配列の最大長を出力するプログラムをC++で作成することです。

例で問題を理解しよう

入力 − array = {'t', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i', 'n', 't'}

出力 − 14

説明 −

この部分配列 {'t', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i', 'n', 't'} は、先頭と末尾がどちらも 't' になっています。

解決アプローチ

この問題を解くには、配列内の各文字について最初に出現する位置（first occurrence）と最後に出現する位置（last occurrence）を見つけ、次の公式を使います。

部分配列の長さ = 最後の出現位置 − 最初の出現位置 + 1

すべての文字について計算した結果の中から、最大の長さを求めればよいのです。

具体例で解き方を確認

Array = {a, b, a, c, b, a} の場合を考えてみましょう。

• 要素 'a'：最初の出現位置はインデックス0、最後の出現位置はインデックス5
  部分配列の長さ = 5 − 0 + 1 = 6
• 要素 'b'：最初の出現位置はインデックス1、最後の出現位置はインデックス4
  部分配列の長さ = 4 − 1 + 1 = 4

したがって、この配列における最大長（maxLength）は 6 となります。

C++プログラム例

最初と最後の要素が同じ部分配列の最大長を出力するプログラム −

#include <iostream>
using namespace std;
int maxSubArrLength(string arr, int n){
    int firstOccurrence, lastOccurrence = -1;
    int maxlength = 0;
    char ch;
    for (int i = 0; i < n; i++){
        ch = arr[i];
        firstOccurrence = lastOccurrence = i;
        for(int j = i; j<n; j++){
            if(arr[j] == ch)
                lastOccurrence = j;
        }
        maxlength = max(maxlength, (lastOccurrence - firstOccurrence + 1));
    }
    return maxlength;
}
int main(){
    string arr = "tutorialsPoint";
    int n = arr.length();
    cout<<"The maximum length of subarray whose first and last elements are same is "<<maxSubArrLength(arr, n);
    return 0;
}

出力結果

The maximum length of subarray whose first and last elements are same is 14

まとめ

このアルゴリズムは、各文字について最初と最後の出現位置を調べることで、条件を満たす部分配列の最大長をシンプルに求められます。二重ループを使用しているため時間計算量は O(n²) ですが、直感的で実装しやすいのが特徴です。さらに効率化したい場合は、ハッシュマップ（unordered_map）を使って各文字の最初の出現位置を事前に記録しておくことで、計算量を O(n) まで改善することもできます。