RGBRED — SPOJ - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	151

I tried a greedy approach for this problem, here is my solution :

Spoiler

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

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    cout.tie(nullptr);
#ifdef HELL_JUDGE
    freopen("input","r",stdin);
    freopen("output","w",stdout);
#endif
    int t; cin >> t; 
    while (t--) {
        int n; cin >> n; 
        string s; cin >> s; 
        deque<char>d; 
        d.push_back(s[0]); 
        map<char,int>m; 
        m['G'] =1;
        m['R'] =2;
        m['B'] =3;
        map<int,char>rm; 
        rm[1] ='G';
        rm[2] ='R';
        rm[3] ='B';
        for(int i=1 ; i<n; ++i) {
            if(d.back() != s[i]) {
                char ch = d.back(); d.pop_back(); 
                ch = rm[m[ch]^m[s[i]]];
                while (!d.empty() && d.back() != ch) {
                    char temp = d.back(); d.pop_back();
                    ch = rm[m[ch]^m[temp]];
                }
                d.push_back(ch);
           } else {
               d.push_back(s[i]);
           }
        }
        cout << d.size() << '\n'; 
    }
    return 0;
}

But this gave me WA. So I found a test case also:

Spoiler

1
7
RGRRGRR

answer should be 1 , but my code gives 3. I guess this is DP problem. Can anyone please help.

hello_hell's blog