오늘은 3월 리트코딩 챌린지 8번째 문제를 풀어보겠습니다.

문제 설명

문자 'a'와 'b'로만 구성된 문자열 s가 주어집니다. 단일 단계에서 s에서 하나의 회문 하위 시퀀스를 제거할 수 있습니다.

주어진 문자열을 비우기 위한 최소 단계 수를 반환합니다.

문자열은 순서를 변경하지 않고 주어진 문자열의 일부 문자를 삭제하여 생성된 경우 주어진 문자열의 하위 시퀀스입니다.

앞에서 읽을 때와 뒤에서 읽을 때 같은 문자열을 팰린드롬(palindrome)이라고 합니다.

예 1:

**Input:** s = "ababa"
**Output:** 1
**Explanation:** String is already palindrome

예 2:

**Input:** s = "abb"
**Output:** 2
**Explanation:** "**a**bb" -> "**bb**" -> "". 
Remove palindromic subsequence "a" then "bb".

예 3:

**Input:** s = "baabb"
**Output:** 2
**Explanation:** "**baa**b**b**" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

예 4:

**Input:** s = ""
**Output:** 0

해결책

빈 문자열을 얻으면 삭제할 것이 없기 때문에 0을 반환할 수 있습니다.

회문이 있는 경우 회문을 한 번에 제거할 수 있으므로 1을 반환할 수 있습니다.

그렇지 않은 경우 2를 반환할 수 있습니다. (처음에는 'a' 또는 'b'를 제거한 다음 나머지 문자열을 제거할 수 있습니다.)

시간 복잡도:O(n), n은 문자열의 길이

공간 복잡도:O(1), 추가 공간이 사용되지 않음

코드는 다음 저장소에서 찾을 수 있습니다.

<사업부 클래스="ltag-github-body">

2021년 3월 리트코딩 챌린지 이전 문제를 모두 올렸습니다. 확인하실 수 있습니다.

<올>

March LeetCoding Challenge — Day 1 — Distribute Candies

March LeetCoding Challenge — Day 2 — Set Mismatch

March LeetCoding Challenge — Day 3 — Missing Number

March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists

March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree

March LeetCoding Challenge — Day 6 — Short Encoding of Words