문자열 s와 값 k가 있다고 가정합니다. k의 값은 s의 길이의 인수이며 길이가 n이라고 가정합니다. s를 k 크기의 t_i라고 하는 n/k개의 서로 다른 부분 문자열로 나눌 수 있습니다. 그런 다음 이 t_i를 사용하여 u_i를 다음과 같이 만듭니다.
-
u_i에 있는 문자는 t_i에 있는 문자의 하위 시퀀스입니다.
-
u_i의 각 문자 빈도가 1이 되도록 반복 문자는 이 문자열에서 제거됩니다.
이 u_i 문자열을 찾아야 합니다.
따라서 입력이 s ="MMPQMMMRM" k =3과 같으면 출력은 ["MP", "QM", "MR"]이 됩니다. s의 크기는 9이고 k는 3이므로 9/ 3 =3. 문자열은 MMP, QMM 및 MRM이지만 중복 문자를 지원하지 않으므로 MP, QM 및 MR이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- i :=0
- ret :=새 목록
- mp :=새 지도
- to_print :=빈 문자열
- i
- i mod k가 0과 같고 i가 0이 아닌 경우
- ret 끝에 to_print 삽입
- mp 지우기 및 to_print 지우기
- s[i]가 mp에 없으면
- mp[s[i]] :=0
- to_print :=to_print + s[i]
- 나는 :=나는 + 1
- i mod k가 0과 같고 i가 0이 아닌 경우
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(s, k): i = 0 ret = [] mp, to_print = {}, "" while i < len(s): if i % k == 0 and i != 0: ret.append(to_print) mp, to_print = {}, "" if s[i] not in mp.keys(): mp[s[i]] = 0 to_print += s[i] i += 1 ret.append(to_print) return ret s = "MMPQMMMRM" k = 3 print(solve(s, k))
입력
"MMPQMMMRM", 3
출력
['MP', 'QM', 'MR']