CF578E Walking!

爱丽丝家门前有一条沙地小径。 白天，人们走在上面，留下了一连串的脚印。每一步都会留一个脚印。爱丽丝无法区分这些脚印被踩的顺序，但她能分辨出每个脚印是左脚还是右脚。同时她确定，所有的人都是交替用左脚和右脚行走的。 例如，假设有一个人走过小径，留下了一串脚印，按顺序排列为 $RRLRL$（'R' 表示右脚，'L' 表示左脚）。你可能会觉得脚印的排列很奇怪。但实际上，有些步骤是倒退走造成的！ 例如，可能有如下踩踏的顺序得到这串脚印，如 $1\rightarrow3\rightarrow2\rightarrow5\rightarrow4$ 或 $2\rightarrow3\rightarrow4\rightarrow5\rightarrow1$（我们假定每两步之间的距离可以任意远）。这两个方案中倒退走的步数分别为 $2$ 和 $1$。 爱丽丝对这些脚印十分感兴趣。每当有人走过小径，她就把所有脚印拍照，然后把它们擦掉，这样下一个人留下的就又是一组新的脚印。我们已知人们是交替用右脚和左脚走路的，但第一步可能是左脚，也可能是右脚。 爱丽丝想知道，某个人最少倒退走了多少步。这个问题有点难，请你帮帮爱丽丝计算这个最小的倒退步数，并构造出一种可能的踩踏顺序。

仅一行，包含字符串 $S$（$1 \leq |S| \leq 100000$），从入口到出口依次记录所有脚印。'R' 表示右脚，'L' 表示左脚。 保证至少存在一种合法的踩踏顺序。

输出两行。 第一行输出一个数，表示最小可能的倒退步数。 第二行输出 $|S|$ 的一个全排列，表示一种可能的踩踏顺序（用 $1$ 到 $|S|$ 的整数表示，对于长度为 $n$ 的输入字符串 $S$，表示第 $a_1,a_2,\ldots,a_n$ 个脚印依次踩踏）。 若有多种方案，输出其中任意一种均可。

对于第一个样例，有一种可能的顺序为 $2\rightarrow5\rightarrow1\rightarrow3\rightarrow4$，其中只有 $5\rightarrow1$ 是倒退步，因此答案是 $1$。 对于第二个样例，直接按输入顺序行走即可，无需倒退步。 对于第三个样例，每次从 L 到 R 都是倒退步，因此会有 $4$ 次倒退步。 由 ChatGPT 5 翻译