この問題は、双方向リストを用いることで直接解くことができます。

双方向リストは、任意の位置の挿入と削除が \(O(1)\) 、検索が \(O(\rm{distance})\) かかるデータ構造です。

双方向リストのイテレータを用意し、初めは末尾の位置にいるものとします。 また、イテレータに対して挿入操作を行った場合、見ている位置の直前に値が挿入されるものとします。 与えられる操作を次のように実行することで、正しい答えを得ることができます。

• \(s_i\) が L ならば、イテレータを一つ戻し、値を挿入する。
• \(s_i\) が R ならば、値を挿入する。

C++による実装例

#include<iostream>
#include<list>
#include<string>
int main() {
  int N;
  std::string S;
  std::cin >> N >> S;
  std::list<int> A{0};
  std::list<int>::iterator iter = A.end();
  for (int i = 0;i < N;++ i) {
    if (S[i] == 'L') -- iter;
    A.insert(iter, i + 1);
  }
  for (int i : A) std::cout << i << ' ';
  return 0;
}

Javaによる実装例

import java.util.*;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      char[] S = sc.next().toCharArray();
      LinkedList<Integer> list = new LinkedList<>();
      list.add(0);
      ListIterator<Integer> iter = list.listIterator();
      iter.next();
      for (int i = 0;i < N;++ i) {
        if (S[i] == 'L') iter.previous();
        iter.add(i + 1);
      }
      for (int i : list) System.out.print(i + " ");
    }
  }
}