아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

SKH 문자열

시간 제한1초메모리 제한1024 MB

요약
주어진 문자열 T의 임의 위치에 S를 p개, K를 q개, H를 r개 삽입해 연속한 "SKH" 부분 문자열의 개수를 최대로 만든다.
난이도

보통10점 중 7점

유형
동적 계획법, 문자열, 그리디
정답자
아직 제출이 없습니다

문제

알파벳 대문자 'S', 'K', 'H'로 이루어진 길이 NN의 문자열 TT가 주어진다.

주어진 문자열 TT의 임의의 위치에 'S'를 pp개, 'K'를 qq개, 'H'를 rr개 삽입해서 만든 문자열에서 "SKH"의 최대 등장 횟수를 구하라. 

"SKH"는 연결되어 있을 때 한 번으로 센다.

입력

첫째 줄에 문자열의 길이 N(1≤N≤100,000)N(1 \le N \le 100\\,000), 'S'를 삽입 가능한 횟수 pp, 'K'를 삽입 가능한 횟수 qq, 'H'를 삽입 가능한 횟수 rr이 주어진다. (0≤p+q+r≤100,000)(0 \le p+q+r \le 100\\,000)

둘째 줄에 'S', 'K', 'H'로만 구성된 문자열 TT가 주어진다.

출력

"SKH"를 가장 많이 포함하도록 'S'를 pp개, 'K'를 qq개, 'H'를 rr개 삽입해서 만든 문자열에서 "SKH"의 최대 등장 횟수를 출력하라.

예제3

  1. 예제 1

    입력
    7 3 4 2
    SKSSKHS
    
    예상 출력
    3
    
  2. 예제 2

    입력
    9 4 3 3
    HKKKSSSSS
    
    예상 출력
    4
    
  3. 예제 3

    입력
    12 3 4 3
    HHHHKKKKSSSS
    
    예상 출력
    5