[LeetCode] 1332 | Remove Palindromic Subsequences | Python

---

문제 링크: https://leetcode.com/problems/remove-palindromic-subsequences/

---

문제

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

---

조건

• 1 <= s.length <= 1000
• s[i] is either 'a' or 'b'.

---

내 풀이

문제를 잘 읽어보면 연속하지 않는 문자가 palindrome이라도 제거 가능하다.

그리고 한 문자로만 이루어진 모든 문자열은 palindrome이다.

그렇기때문에 처음에 주어지는 문자열(s)이 palindrome이면 한번에 제거 가능하니까 1을 리턴하고, 그렇지 않다면 처음 시도에 모든 a를, 두번째 시도에 모든 b를 제거하면 되므로 2를 리턴하면 된다.

---

코드

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        
        def isPalindrome(s):
            left, right = 0, len(s)-1
            while left <= right:
                if s[left] != s[right]:
                    return False
                
                left += 1
                right -= 1
            
            return True
        
        if isPalindrome(s):
            return 1
        else:
            return 2