No.1924 3 color painting on a line
問題文最終更新日: 2022-04-30 02:31:26
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Problem Statement
There were $N$ pure white cells arranged in a row. YUKI wants to paint the cells using paint of 3 colors: red, green, and blue.
A string $S$ of $N$ characters represents the coloring YUKI has in mind.
If the $i$-th ($1 \leq i \leq N$) character $S[i]$ is R, she wants to paint the $i$-th cell from the front red; if it is G, green; and if it is B, blue.
- Choose integers $L, R$ satisfying $1 \leq L \leq R \leq N$, and fill the $L, L+1, \ldots, R$-th cells from the front with a single color of your choice. Cells that have already been painted are overwritten.
Input
$N$ $S$
The integer $N$ is given on the first line, and the string $S$ is given on the 2nd line.
- $1 \leq N \leq 10^5$
- $S$ is a string consisting of
R,G, andB
Output
Output the minimum number of operations needed to obtain the coloring represented by $S$.
Sample
Sample 1
Input
1 R
Output
1
Sample 2
Input
3 RGR
Output
2
Sample 3
Input
3 RGB
Output
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
37zigen