Shortest Majority Substring in C++

สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s เราต้องหาความยาวของสตริงย่อย (substring) ที่สั้นที่สุด (ความยาวขั้นต่ำคือ 2) ที่ทำให้ตัวอักษรบางตัวปรากฏมากกว่าตัวอักษรอื่นๆ รวมกัน หากไม่พบคำตอบ ให้คืนค่า -1

เช่น หากอินพุตคือ "abbbcde" ผลลัพธ์จะเป็น 2 เนื่องจากสตริงย่อย "bb" มีความยาวน้อยที่สุดและตัวอักษร 'b' ปรากฏมากกว่าตัวอื่นรวมกัน

ขั้นตอนการแก้ปัญหา

• สังเกตว่าสตริงย่อยที่สั้นที่สุดที่เป็นไปได้คือความยาว 2 (ตัวอักษรซ้ำติดกัน) หรือ 3 (รูปแบบ aba)
• ตรวจสอบทุกตำแหน่ง i:
  • ถ้า s[i] == s[i+1]: คืนค่า 2 ทันที
  • ถ้า s[i] == s[i+2]: จดจำว่ามีคำตอบความยาว 3
• คืนค่า 3 ถ้าพบรูปแบบ aba, ไม่เช่นนั้น -1

ตัวอย่างโค้ด

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

class Solution {
public:
    bool ok(vector<int>& cnt) {
        int total = 0, maxVal = 0;
        for (auto& it : cnt) {
            total += it;
            maxVal = max(maxVal, it);
        }
        return maxVal > (total - maxVal);
    }
    int solve(string s) {
        int n = s.size();
        int 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"));
}

อินพุต

"abbbcde"

เอาต์พุต

2