Chuỗi conMajority ngắn nhất trong C++

Cho chuỗi chữ thường s. Tìm độ dài chuỗi con ngắn nhất (tối thiểu 2) mà có 1 ký tự xuất hiện nhiều hơn tổng các ký tự còn lại. Không tìm thấy → -1.

Ví dụ: "abbbcde" → "bb" độ dài 2.

Quan sát quan trọng

• Nếu có 2 ký tự liên tiếp giống nhau → độ dài 2 (tối thiểu).
• Nếu có mẫu x_y_x (ký tự đầu = ký tự thứ 3) → độ dài 3.
• Không có 2 trường hợp trên → không tồn tại chuỗi con thỏa mãn (chứng minh: chuỗi con dài hơn luôn chứa 1 trong 2 pattern trên).

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(string s) {
        int n = s.size(), ret = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (i+1 < n && s[i] == s[i+1]) return 2;
            else if (i+2 < n && s[i] == s[i+2]) ret = 3;
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

int main() {
    Solution ob;
    cout << ob.solve("abbbcde");
    return 0;
}

Đầu ra

2