Regard the string as S\(S\)R. In other words, prepend an S and append an R to \(S\).
We also mandate that the added characters cannot be modified.

Then the string is always in the form of (consecutive S)(consecutive R)(consecutive S)\(\dots\)(consecutive R).
Therefore, if we let \(a\) be the number of positions that R and S occur consecutively in this order, and \(b\) be the number of positions that different characters occur consecutively, then \(a=(b-1)/2\) always holds. Therefore, we may alter the goal of increasing \(a\) into increasing \(b\) by the operations.

Additionally, consider transforming the SR-sequence of length \((N+2)\) with a 01-sequence of length \((N+1)\) by corresponding different adjacent characters with 1 and the same adjacent character with 0.
For example, SRSSRRRRSR is transformed to 110100011.
What does it mean to the 01-sequence to toggle a specific character in the SR-sequence (that is not at both ends)?

Modifying an element (that is not at both ends) in the SR-sequence corresponds to modifying two adjacent characters in the 01-sequence.
For example, SR[S]SRRRRSR \(\rightarrow\) SR[R]SRRRRSR corresponds to 1[10]100011 \(\rightarrow\) 1[01]100011.

This problem is boiled down to increasing the occurrences of 1 in the 01-sequences using the two-element update mentioned above with minimum number of steps.

The number of 1 increases only when operating on two adjacent 0s.
Also, operating on 01 to turn it into 10 (or vice versa) can be interpreted as moving the position of 0 to the immediate left or right.
Moreover, we can prove that we do not need to operate on two adjacent 1s.

Therefore, the problem is reduced to pairing 0s.
For example, if the 01-sequence is 10100101, the 0s are at positions \(2,4,5,7\). Then it turns out optimal that:

• If we want to increase a total of two 1s, pair the 0s at positions \(4\) and \(5\).
• If we want to increase a total of four 1s, pair the 0s at positions \(2\) and \(4\), and \(5\) and \(7\).

Here, let us transform the information on the positions of 0s into an array \(D\) containing the distances between adjacent 0s.
If the 0s are at positions \(2,4,5,7\), we have \(D=(2,1,2)\).

Using this \(D\), the problem can be rephrased as follows:

In order to increase the number of 1s by \(k\), choose \(k/2\) elements from \(D\). Minimize the sum of the chosen elements.
Here, no two adjacent elements must not be simultaneously chosen (because the same 0 cannot be paired with multiple other 0s).

Now this problem is identical to the following problem:

• JOI ²⁰¹⁷⁄₂₀₁₈ Spring Training Day 4 Problem 1 飴 (Candies) (Problem statement is in Japanese)
  • AtCoder Judge
  • Official editorial

The solution is the following greedy algorithm:

• Suppose you choose an element \(D_i\) in \(D\).
• Then, remove \(D_{i-1},D_{i}\), and \(D_{i+1}\), and insert \(D_{i-1}+D_{i+1}-D_i\) here.
• Repeat choosing the smallest element while obeying the rules above.

This can be implemented by properly using a priority queue and a linked list. The total time complexity is \(O(N \log N)\).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int T;
  cin >> T;
  while(T--){
    int n;
    string s;
    cin >> n >> s;
    s="S"+s+"R";
    int val=0;
    vector<int> sam;
    for(int i=0;i<=n;i++){
      if(s[i]==s[i+1]){
        sam.push_back(i);
      }
      else{val++;}
    }
    val/=2;
    vector<int> d;
    d.push_back(1e8); d.push_back(1e8);
    for(int i=1;i<sam.size();i++){
      d.push_back(sam[i]-sam[i-1]);
    }
    d.push_back(1e8); d.push_back(1e8);
    int dl=d.size();
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    vector<int> lef(dl),rig(dl);
    vector<int> alive(dl,1);
    for(int i=0;i<dl;i++){
      lef[i]=i-1;
      rig[i]=i+1;
      pq.push({d[i],i});
    }
    vector<int> res(n+1,0);
    int hand=0;
    res[hand]=val;
    while(val<(n/2)){
      auto od=pq.top(); pq.pop();
      if(alive[od.second]==0){continue;}
      hand+=od.first; val++;
      res[hand]=val;
      int el=lef[od.second];
      int er=rig[od.second];
      d[od.second]=d[el]+d[er]-d[od.second];
      pq.push({d[od.second],od.second});
      {
        alive[el]=0;
        int x=lef[el],y=rig[el];
        lef[y]=x; rig[x]=y;
      }
      {
        alive[er]=0;
        int x=lef[er],y=rig[er];
        lef[y]=x; rig[x]=y;
      }
    }
    for(int i=1;i<=n;i++){res[i]=max(res[i],res[i-1]);}
    for(int i=0;i<=n;i++){
      if(i){cout << " ";}
      cout << res[i];
    }cout << "\n";
  }
  return 0;
}