关注我，分享高质量每日一题题解~

b站同名账号分享力扣杯历届真题视频题解，也欢迎大家提出宝贵意见！

思路：贪心

• 最终的字符串，要么全为白色，要么全为黑色。
• 以目标全为白色为例，遍历字符串的前 $n - 1$ 个砖块，每遇到一个黑色砖块，就对其进行一次操作，将该砖块和下一个砖块变为另一种颜色，并将结果记录到数组中。如果发现最后一个砖块不为白色，那说明无法将砖块全部转化为白色；黑色同理。
• 若最终全转化为白色和全转化为黑色均不可行，则输出 $-1$，否则输出一种可行的方案即可。

代码（C++）

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

int main() {
    int T = 1;
    cin >> T;
    while(T--) {

        int n;
        cin >> n;
        string s;
        cin >> s;
        string t = s;

        int ret1 = 0, ret2 = 0;

        vector<int> v, w;
        for(int i = 0; i < n - 1; i++) {

            // 全部转化为黑色砖块
            if(s[i] == 'W') {
                s[i] = 'B';
                // 将第 i 和 i + 1 个砖块进行颜色翻转
                if(s[i + 1] == 'W') s[i + 1] = 'B';
                else s[i + 1] = 'W';
                v.push_back(i + 1);
                ret1++;
            }

            // 全部转化为白色砖块
            if(t[i] == 'B') {
                t[i] = 'W';
                if(t[i + 1] == 'W') t[i + 1] = 'B';
                else t[i + 1] = 'W';
                w.push_back(i + 1);
                ret2++;
            }
        }



        if(s[n - 1] != 'B' && t[n - 1] != 'W') {
            cout << -1 << endl;
        } else if(s[n - 1] != 'B') {
            cout << ret2 << endl;
            for(int op : w) cout << op << " ";
            if(ret2) cout << endl;
        } else {
            cout << ret1 << endl;
            for(int op : v) cout << op << " ";
            if(ret1) cout << endl;
        }


    }
    return 0;
}

时间复杂度：$O(n)$