[LeetCode] Delete Characters to Make Fancy String

1.문제

A fancy string is a string where no three consecutive characters are equal.

Given a string s, delete the minimum possible number of characters from s to make it fancy.

Return the final string after the deletion. It can be shown that the answer will always be unique.

fancy string은 단어에서 중복되어 연속으로 나타나는 철자가 3개 미만인 단어를 뜻한다.

문자열 s가 주어질 때 s를 fancy string으로 만들기위해 s의 철자를 삭제하는데, 삭제 횟수의 최솟값을 리턴하는 문제이다.

Example 1

Input: s = "leeetcode"
Output: "leetcode"
Explanation:
Remove an 'e' from the first group of 'e's to create "leetcode".
No three consecutive characters are equal, so return "leetcode".

Example 2

Input: s = "aaabaaaa"
Output: "aabaa"
Explanation:
Remove an 'a' from the first group of 'a's to create "aabaaaa".
Remove two 'a's from the second group of 'a's to create "aabaa".
No three consecutive characters are equal, so return "aabaa".

Example 3

Input: s = "aab"
Output: "aab"
Explanation: No three consecutive characters are equal, so return "aab".

Constraints:

• 1 <= s.length <= 105
• s consists only of lowercase English letters.

2.풀이

1. 문자열의 가장 앞 철자를 stack에 넣고 count 를 1로 초기화 한다.
2. 현재 철자와 stack의 가장 위에 있는 철자를 비교한다.
3. 현재 철자와 top이 같고 count < 2이면 stack에 현재 철자를 넣는다.
4. 현재 철자와 top이 같고 count === 2 이면 같은 철자가 연속해서 3번 나온 경우이다.

/**
 * @param {string} s
 * @return {string}
 */
const makeFancyString = function (s) {
  let count = 1;
  const stack = [s[0]];
  let top = "";

  for (let i = 1; i < s.length; i++) {
    // 스택의 가장 윗 요소를 꺼낸다.
    top = stack[stack.length - 1];
    if (top === s[i] && count < 2) {
      // 현재 단어와 top이 같고 count < 2 이면 현재 단어를 stack에 쌓는다
      stack.push(s[i]);
      count++;
    } else if (top !== s[i]) {
      // 현재 단어와 top 이 다르면 stack에 현재 단어를 쌓고 count를 1로 초기화한다.
      stack.push(s[i]);
      count = 1;
    } else if (top === s[i] && count === 2) {
      // top과 현재단어가 같고 count === 2이면 중복된 단어가 3이상이 되는 경우이므로 스택에 쌓지 않는다.
      continue;
    }
  }

  return stack.join("");
};

3.결과