1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int MAXN = 1000111;

char a[MAXN];
int prefix_rs[MAXN];
int suffix_ls[MAXN];
int ans[MAXN];

int main(){
    int n; scanf("%d", &n);
    scanf("%s", a+1);
    for (int i=1; i<=n; i++){
        prefix_rs[i] = prefix_rs[i-1] + (a[i] == 'P' ? 1 : 0);
    }
    for(int i=n; i>=1; i--){
        suffix_ls[i] = suffix_ls[i+1] + (a[i] == 'L' ? 1 : 0);
    }
    
    for(int i=1; i<=n; i++){
        // L: prefix_rs-1, suffix_ls-1, prefix_rs-1, suffix_ls-=1, etc...
        // then: quantity of rightward hits: min(prefix_rs, suffix_ls+1)
        // quantity of leftward hits: min(prefix_rs, suffix_ls)
        // printf("%d: %c sufL %d prefr %d\n", i, a[i], suffix_ls[i], prefix_rs[i]);
        if (a[i] == 'L'){
            ans[i] = min(prefix_rs[i-1], suffix_ls[i+1]+1) + min(prefix_rs[i-1], suffix_ls[i+1]);
        }
        else{
            ans[i] = min(suffix_ls[i+1], prefix_rs[i-1]+1) + min(suffix_ls[i+1], prefix_rs[i-1]);
        }
        printf("%d ", ans[i]);
    }
    printf("\n");
    
}