문제
KSAAC 운영진은 모두 KSA를 사랑하기 때문에 다음 조건을 만족하는 문자열을 좋아한다.
문자열의 길이를 $N$이라고 할 때, 1ドル \leq i \leq N$인 모든 $i$에 대하여
- $i$를 3ドル$으로 나눈 나머지가 1ドル$이면 $i$번째 문자는
K이다.
- $i$를 3ドル$으로 나눈 나머지가 2ドル$이면 $i$번째 문자는
S이다.
- $i$를 3ドル$으로 나눈 나머지가 0ドル$이면 $i$번째 문자는
A이다.
빈 문자열 또한 KSAAC 운영진이 좋아하는 문자열이다.
문자열에는 다음 시행을 0ドル$회 이상 할 수 있으며 매회 둘 중 하나를 선택하여 시행할 수 있다.
- 존재하는 아무 문자를 한 개 제거한다.
- 존재하는 아무 문자 한 개를 맨 앞으로 옮긴다.
주어진 문자열 $X$에 적절한 시행을 하여 $X$를 가능한 최대 길이의 KSAAC 운영진이 좋아하는 문자열로 바꾸려고 한다. 이때 필요한 시행의 최소 횟수를 구하여라.
출력
문자열 $X$를 가능한 최대 길이의 KSAAC 운영진이 좋아하는 문자열로 바꾸기 위한 최소 시행 횟수를 출력한다.
제한
- 1ドル \le |X| \le 5 \times 10^5$
- $X_i \in \{ $
K,ドル $S,ドル $A$ \}$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 10 | $X$에 K가 정확히 한 개 존재
|
| 2 | 40 | $X$에 존재하는 K, S, A의 개수가 동일
|
| 3 | 50 | 추가 제약 조건 없음
|
W3sicHJvYmxlbV9pZCI6IjMzNDk1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiS1NBIFx1YmIzOFx1Yzc5MFx1YzVmNCAyIiwiZGVzY3JpcHRpb24iOiI8cD5LU0FBQyBcdWM2YjRcdWM2MDFcdWM5YzRcdWM3NDAgXHViYWE4XHViNDUwIEtTQVx1Yjk3YyBcdWMwYWNcdWI3OTFcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgJE4kXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU2MCBcdWI1NGMsICQxIFxcbGVxIGkgXFxsZXEgTiRcdWM3NzggXHViYWE4XHViNGUwICRpJFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWM8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kaSRcdWI5N2MgJDMkXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWFjMDAgJDEkXHVjNzc0XHViYTc0ICRpJFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWIyOTQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPks8XC9jb2RlPjxcL3NwYW4+XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kaSRcdWI5N2MgJDMkXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWFjMDAgJDIkXHVjNzc0XHViYTc0ICRpJFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWIyOTQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlM8XC9jb2RlPjxcL3NwYW4+XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kaSRcdWI5N2MgJDMkXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWFjMDAgJDAkXHVjNzc0XHViYTc0ICRpJFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWIyOTQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkE8XC9jb2RlPjxcL3NwYW4+XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHViNjEwXHVkNTVjIEtTQUFDIFx1YzZiNFx1YzYwMVx1YzljNFx1Yzc3NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiA8XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHViMjk0IFx1YjJlNFx1Yzc0YyBcdWMyZGNcdWQ1ODlcdWM3NDQgJDAkXHVkNjhjIFx1Yzc3NFx1YzBjMSBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCBcdWI5ZTRcdWQ2OGMgXHViNDU4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHVjNWVjIFx1YzJkY1x1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiA8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVjNTQ0XHViYjM0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWQ1NWMgXHVhYzFjIFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YzU0NFx1YmIzNCBcdWJiMzhcdWM3OTAgXHVkNTVjIFx1YWMxY1x1Yjk3YyBcdWI5ZTggXHVjNTVlXHVjNzNjXHViODVjIFx1YzYyZVx1YWUzNFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0ICRYJFx1YzVkMCBcdWM4MDFcdWM4MDhcdWQ1NWMgXHVjMmRjXHVkNTg5XHVjNzQ0IFx1ZDU1OFx1YzVlYyAkWCRcdWI5N2MgPHN0cm9uZz5cdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHViMzAwIFx1YWUzOFx1Yzc3NDxcL3N0cm9uZz5cdWM3NTggS1NBQUMgXHVjNmI0XHVjNjAxXHVjOWM0XHVjNzc0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViYzE0XHVhZmI4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWQ1ODlcdWM3NTggPHN0cm9uZz5cdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4PFwvc3Ryb25nPlx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFgkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJiMzhcdWM3OTBcdWM1ZjQgJFgkXHViOTdjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWIzMDAgXHVhZTM4XHVjNzc0XHVjNzU4IEtTQUFDIFx1YzZiNFx1YzYwMVx1YzljNFx1Yzc3NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YmMxNFx1YWZiOFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1ZDU4OSBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIHxYfCBcXGxlIDUgXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kWF9pIFxcaW4gXFx7ICQ8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+SzxcL2NvZGU+PFwvc3Bhbj4kLCAkPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlM8XC9jb2RlPjxcL3NwYW4+JCwgJDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5BPFwvY29kZT48XC9zcGFuPiQgXFx9JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kWCRcdWM1ZDAgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPks8XC9jb2RlPjxcL3NwYW4+XHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHVhYzFjIFx1Yzg3NFx1YzdhYzxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JFgkXHVjNWQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+SzxcL2NvZGU+PFwvc3Bhbj4sIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5TPFwvY29kZT48XC9zcGFuPiwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkE8XC9jb2RlPjxcL3NwYW4+XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWIzZDlcdWM3N2M8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPlx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0IFx1YzVjNlx1Yzc0YzxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMzNDk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS1NBIFN0cmluZyAyIiwiZGVzY3JpcHRpb24iOiI8cD5CZWNhdXNlIHRoZSBLU0FBQyBzdGFmZiBsb3ZlIEtTQSwgdGhleSBsaWtlIHN0cmluZ3MgdGhhdCBzYXRpc2Z5IHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hlbiB0aGUgbGVuZ3RoIG9mIHRoZSBzdHJpbmcgaXMgJE4kLCBmb3IgYWxsICRpJCBzdWNoIHRoYXQgJDEgXFxsZXEgaSBcXGxlcSBOJDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPklmIHRoZSByZW1haW5kZXIgYWZ0ZXIgZGl2aWRpbmcgJGkkIGJ5ICQzJCBpcyAkMSQsIHRoZSAkaSR0aCBjaGFyYWN0ZXIgaXMgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPks8XC9jb2RlPjxcL3NwYW4+LjxcL2xpPlxyXG5cdDxsaT5JZiB0aGUgcmVtYWluZGVyIGFmdGVyIGRpdmlkaW5nICRpJCBieSAkMyQgaXMgJDIkLCB0aGUgJGkkdGggY2hhcmFjdGVyIGlzIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5TPFwvY29kZT48XC9zcGFuPi4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgdGhlIHJlbWFpbmRlciBhZnRlciBkaXZpZGluZyAkaSQgYnkgJDMkIGlzICQwJCwgdGhlICRpJHRoIGNoYXJhY3RlciBpcyA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+QTxcL2NvZGU+PFwvc3Bhbj4uJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QW4gZW1wdHkgc3RyaW5nIGlzIGFsc28gdGhlIHN0cmluZyB3aGljaCB0aGUgS1NBQUMgc3RhZmYgbGlrZS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBvcGVyYXRpb25zIGNhbiBiZSBwZXJmb3JtZWQmbmJzcDskMCQgb3IgbW9yZSB0aW1lcyBvbiB0aGUgc3RyaW5nIGFuZCBvbmUgb2YgdGhlIHR3byBjYW4gYmUgc2VsZWN0ZWQgZWFjaCB0aW1lLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlJlbW92ZSBvbmUgY2hhcmFjdGVyIGZyb20gdGhlIHN0cmluZy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+TW92ZSBvbmUgY2hhcmFjdGVyIHRvIHRoZSBiZWdpbm5pbmcgb2YgdGhlIHN0cmluZy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5CeSBwZXJmb3JtaW5nIG9wZXJhdGlvbnMgb24gdGhlIGdpdmVuIHN0cmluZyAkWCQsIHdlIHRyeSB0byBjaGFuZ2UgJFgkIGludG8gYSBzdHJpbmcgb2YgdGhlIDxzdHJvbmc+bWF4aW11bSBwb3NzaWJsZSBsZW5ndGg8XC9zdHJvbmc+LCB3aGljaCB0aGUgS1NBQUMgc3RhZmYgbGlrZS4gRmluZCB0aGUgPHN0cm9uZz5taW5pbXVtIG51bWJlciBvZiBvcGVyYXRpb25zPFwvc3Ryb25nPiByZXF1aXJlZCBmb3IgaXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhIHN0cmluZyAkWCQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgbmVlZGVkIHRvIGNoYW5nZSB0aGUgZ2l2ZW4gc3RyaW5nICRYJCBpbnRvIGEgc3RyaW5nIG9mIHRoZSBtYXhpbXVtIHBvc3NpYmxlIGxlbmd0aCwgd2hpY2ggdGhlIEtTQUFDIHN0YWZmIGxpa2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIHxYfCBcXGxlIDUgXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kWF9pIFxcaW4gXFx7ICQ8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+SzxcL2NvZGU+PFwvc3Bhbj4kLCAkPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlM8XC9jb2RlPjxcL3NwYW4+JCwgJDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5BPFwvY29kZT48XC9zcGFuPiQgXFx9JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5UaGVyZSBpcyBleGFjdGx5IG9uZSA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+SzxcL2NvZGU+PFwvc3Bhbj4gaW4gc3RyaW5nICRYJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+VGhlIG51bWJlcnMgb2YgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPks8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UzxcL2NvZGU+PFwvc3Bhbj4sIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5BPFwvY29kZT48XC9zcGFuPiBpbiBzdHJpbmcgJFgkIGFyZSB0aGUgc2FtZTxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50czxcL3A+XHJcbiJ9XQ==