[LC] 1405. Longest Happy String

[seungriyou]

https://leetcode.com/problems/longest-happy-string/ similar to #70

Approach

마찬가지로 greedy 방식으로 접근한다.

1. cnt 값이 0이 아닌 것에 대해서 priority queue [(-cnt, char)] 구성 (max heap)

2. priority queue를 이용하여 limit이 가장 높은 문자 ch1 pop

3. res에 가장 최근 추가된 두 문자와 ch1이 같다면,

   1. limit이 두 번째로 높은 문자 ch2 pop

      ➡️ 이때, priority queue가 비어있다면, 현재의 res를 곧바로 return

   2. ch2를 res에 추가하고, cnt2 업데이트하여 (0이 아니면) priority queue에 다시 넣기

   3. ch1은 그대로 다시 priority queue에 넣기

4. 3번에 해당하지 않는다면 ch1을 res에 추가하고, cnt1 업데이트하여 (0이 아니면) priority queue에 다시 넣기

5. res 반환

Complexity

• Time: O(nlog3) = O(n)
• Space: O(n) (res는 결과 반환에 사용되므로 pq만 고려해서 O(1)이라고 해도 되나..?)