[LC] 984. String Without AAA or BBB

[seungriyou]

https://leetcode.com/problems/string-without-aaa-or-bbb/ similar to #70

Approach

Idea 1: Max Heap

78 문제와 동일하게 priority queue를 max heap으로 사용하여, 동일한 문자가 세 번 연달아 뽑힐 때는 다음 문자를 뽑는 방식으로 풀 수 있다.

단, s를 만들 수 있다는 것이 보장되어 있으므로 루프 내에서 예외 처리를 하지 않아도 된다.

Idea 2: Iterative

s를 만들 수 있다는 것이 보장되어 있고, 문자가 두 가지 밖에 없기 때문에 다음과 같이 풀 수 있다.

• a와 b가 모두 0 보다 클 때

  1. a > b : a -= 2, b -= 1 후 res에 "aab" 추가
  2. a < b : a -= 1, b -= 2 후 res에 "bba" 추가
  3. a == b : a -= 1, b -= 1 후 res에 "ab" 추가

• a와 b 중 하나라도 0이면

  1. 0이 아닌 문자에 대해서는 남은 수만큼 res에 추가

Idea 3: Recursive

Idea 2를 recursive 한 방법으로도 작성할 수 있다.

Complexity

• Time: (max heap) O(nlog2) = O(n) / (나머지) O(n)
• Space: (나머지) O(1) / (recursive) O(n) (recursion stack)