Codeforces Round #306 Div.2 A: Two Substrings — 判斷不重疊 AB 與 BA

問題描述

給定字符串 s (|s| ≤ 10⁵)，判斷是否存在不重疊的子串 AB 和 BA（順序任意）。輸出 YES 或 NO。

關鍵點：不重疊

ABA 中雖有 AB (0-1) 和 BA (1-2)，但共用字符 B，屬於重疊，答案 NO。
需找到兩個不共用任何字符位置的 AB 和 BA。

算法：雙向掃描 + 貪心標記

單向掃描可能漏解（如 ABAXXXAB）。採用正向 + 逆向雙掃描：

1. 正向掃描：優先找 BA，再找 AB（或相反順序），找到後跳過兩字符，標記計數。若兩者均找到 → YES。
2. 若正向失敗，**逆向掃描**（從右向左），同理優先找 AB 再 BA。若成功 → YES。
3. 否則 NO。

雙向掃描覆蓋了所有可能的不重疍分佈情況。

代碼實現

#include 
using namespace std;
bool check(const string& s) {
    int n = s.size();
    // 正向：先BA後AB
    int cntBA = 0, cntAB = 0;
    for (int i = 0; i+1 < n; ) {
        if (s[i]=='B' && s[i+1]=='A' && !cntBA) { cntBA++; i+=2; }
        else if (s[i]=='A' && s[i+1]=='B' && !cntAB) { cntAB++; i+=2; }
        else i++;
    }
    if (cntBA && cntAB) return true;
    // 逆向：先AB後BA
    cntBA = cntAB = 0;
    for (int i = n-1; i > 0; ) {
        if (s[i]=='A' && s[i-1]=='B' && !cntBA) { cntBA++; i-=2; }
        else if (s[i]=='B' && s[i-1]=='A' && !cntAB) { cntAB++; i-=2; }
        else i--;
    }
    return cntBA && cntAB;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while (cin >> s) {
        cout << (check(s) ? "YES" : "NO") << '\n';
    }
    return 0;
}

複雜度

• 時間：O(|s|) 兩次掃描。
• 空間：O(1)。

邊界情況測試

總結

本題看似簡單，關鍵在於「不重疊」條件導致單向貪心可能失效。雙向掃描（正向優先 BA、逆向優先 AB）是簡單有效的解法，代碼短、邏輯清晰、O(n) 通過。體現了競賽中「多方向嘗試覆蓋所有情況」的實用技巧。