解题思路

解法一：暴力。每次遍历得到最长最靠左的子串，然后erase删除。

解法二：

可以维护一个集合，存储当前所有连续相同字符构成的子串的信息（子串长度、左右端点位置）。每次从集合中取出长度最大的子串删除，并更新相邻子串的信息。重复此过程，直到集合为空。时间复杂度为 O(Nlog⁡N)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    char last = s[0];
    int cnt = 1, left = 0;
    map<int, array<int, 3>> mpl, mpr;
    set<array<int, 3>> se;
    
    for (int i = 1; i < n; i++) {
        if (s[i] != last) {
            se.insert({-cnt, left, i - 1});
            mpl[left] = {i - 1, last, cnt};
            mpr[i - 1] = {left, last, cnt};
            left = i;
            cnt = 1;
            last = s[i];
        } else {
            cnt++;
        }
    }
    
    se.insert({-cnt, left, n - 1});
    mpl[left] = {n - 1, last, cnt};
    mpr[n - 1] = {left, last, cnt};
    
    int res = 0;
    while (!se.empty()) {
        auto fi = *se.begin();
        auto [cnt, l, r] = fi;
        char lc = mpr[l - 1][1];
        char rc = mpl[r + 1][1];
        if (lc == rc) {
            int lidx = mpr[l - 1][0];
            int ridx = mpl[r + 1][0];
            int lcnt = mpr[l - 1][2];
            int rcnt = mpl[r + 1][2];
            se.erase({-lcnt, lidx, l - 1});
            se.erase({-rcnt, r + 1, ridx});
            se.insert({-(lcnt + rcnt), lidx, ridx});
            mpl.erase(r + 1);
            mpr.erase(l - 1);
            mpl[lidx] = {ridx, lc};
            mpr[ridx] = {lidx, lc};
        }
        se.erase(fi);
        mpr.erase(l);
        mpl.erase(r);
        if (se.empty()) break;
        res++;
    }
    
    cout << res << "\n";
    return 0;
}