Độ dài mảng con lớn nhất có phần tử đầu và cuối giống nhau trong C++

Trong bài toán này, cho một mảng ký tự. Nhiệm vụ: viết chương trình in độ dài lớn nhất của mảng con có phần tử đầu và cuối giống nhau.

Ví dụ minh họa

Đầu vào: mảng = {'t', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i', 'n', 't'}

Đầu ra: 14

Giải thích: Mảng con {'t', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i', 'n', 't'} bắt đầu và kết thúc bằng 't'.

Phương pháp giải

Tìm lần xuất hiện đầu tiên và cuối cùng của mỗi ký tự, sau đó áp dụng công thức:

độ dài mảng con = lastOccurrence - firstOccurrence + 1

Lấy giá trị lớn nhất của tất cả các ký tự.

Minh họa chi tiết

Mảng = {a, b, a, c, b, a}

• Phần tử 'a': first=0, last=5 → độ dài = 5-0+1 = 6
• Phần tử 'b': first=1, last=4 → độ dài = 4-1+1 = 4
• Kết quả lớn nhất = 6

Chương trình 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;
}

Kết quả

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

Độ phức tạp

• Thời gian: O(n²) - có thể tối ưu thành O(n) bằng cách lưu first/last occurrence trước
• Không gian: O(1)