1392D - Omkar and Bed Wars - CodeForces Solution

// Jay Maa Chamunda
/*
Author: Sahil Anand
Find Me on: https://linktr.ee/sahilanand30
*/
/*-----------------------------{HEADERS}-----------------------------*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
/*--------------------------{Optimizations}--------------------------*/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
/*------------------------------{INLINE MACROS}------------------------------*/
#define ll long long int
#define rep(i, n) for (ll i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define ull unsigned long long int
#define countSetBits(z) __builtin_popcountll(z);
#define vll vector<long long int>
#define LL_MAX __LONG_LONG_MAX__
#define LL_MIN -9223372036854775808
#define PI 3.1415926536
#define mod 1000000007
#define INF 1e18
#define nl endl
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define maxHeap priority_queue<ll>                   // maxElement at the top
#define minHeap priority_queue<ll, vll, greater<ll>> // minElement at the top
#define printWithPrecision(i, x) cout << fixed << setprecision(i) << x << nl
/*----------------------------{PBDS/ORDERED_SET}----------------------------*/
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> pbds;
/*----------------------------{NON-STANDARD I/O}----------------------------*/
#define not_standard                  \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);
/*-------------------------------{FAST I/O}-------------------------------*/
#define FASTIO                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);
/*--------------------------------{MAIN CODE}--------------------------------*/

int main()
{
    FASTIO
    ll t = 1;
    cin >> t;
    while (t--)
    {
        ll n, ans = 0, ct = 1;
        string s;
        cin >> n >> s;
        set<char> st;
        for (auto c : s)
            st.insert(c);
        if (st.size() == 1)
            ans = (n+2)/3;
        else
        {
            deque<char> dq;
            for (auto c : s)
                dq.push_back(c);
            while (dq.front() == 'L')
            {
                dq.push_back('L');
                dq.pop_front();
            }
            while (dq.back() == 'R')
            {
                dq.push_front('R');
                dq.pop_back();
            }
            s = "";
            for (auto c : dq)
                s += c;
            for (ll i = 1; i < n - 1; i++)
            {
                if (s[i] == s[i - 1] && s[i] == s[i + 1])
                {
                    ans++;
                    if(s[i]=='R'){
                        if(i+2<n){
                            if(s[i+2]=='R')s[i+1]='L';
                            else s[i]='L';
                        }
                    }
                    else{
                        if(i+2<n){
                            if(s[i+2]=='R')s[i]='R';
                            else s[i+1]='R';
                        }
                    }
                }
            }
        }
        cout << ans << nl;
    }
    return 0;
}