본문 바로가기

Programming Problems/Strings

k개의 종류로 이루어진 최대 길이 스트링 찾기 Q

ex ) aaaabbbb, k=2 >> aaaabbbb

asdfrttt, k=3 >> frttt



나이브 솔루션 : 긴 섭스트링부터 안에 있는 원소의 수가 맞는지 본다. O(N^3) 알고리즘.


해시 테이블을 이용한 트래킹.

헤드 테일을 곁들여서.


헤드를 늘려 가면서 맵에 원소의 수와 갯수를 체크한다.

갯수가 K 일때 길이를 확인한다.

K 보다 갯수가 많아지만 tail을 앞으로 보내면서 하나씩 뺀다.

갯수가 K일때 길이를 확인한다.

head를 K보다 갯수가 많아질때까지 계속 앞으로 보낸다.

헤드가 끝에 닿으면 계산하고 끝낸다.


O(N) 알고리즘 ..!!