Leetcode 2472. Maximum Number of Non-overlapping Palindrome Substrings

문제

You are given a string s and a positive integer k.

Select a set of non-overlapping substrings from the string s that satisfy the following conditions:

The length of each substring is at least k.
Each substring is a palindrome.
Return the maximum number of substrings in an optimal selection.

A substring is a contiguous sequence of characters within a string.

문자열 s와 양의 정수 k가 주어집니다.

문자열 s에서 다음 조건을 만족하는 서로 겹치지 않는 부분 문자열들을 선택하세요.

• 각 부분 문자열의 길이는 최소 k 이상이어야 합니다.
• 각 부분 문자열은 팰린드롬이어야 합니다.

조건을 만족하도록 부분 문자열들을 선택했을 때, 선택할 수 있는 부분 문자열의 최대 개수를 반환하세요.

부분 문자열(substring) 이란 문자열에서 연속된 문자들의 구간을 의미합니다.

---

예시

입력: s = "abaccdbbd", k = 3

출력: 2

설명:
문자열 s = "abaccdbbd"에서 "aba"와 "dbbd"를 선택할 수 있습니다.

두 부분 문자열 "aba"와 "dbbd"는 모두 팰린드롬이며, 길이가 k = 3 이상입니다.

조건을 만족하는 부분 문자열을 2개보다 많이 선택하는 것은 불가능하므로, 정답은 2입니다.

---

제한

• $1 <= k <= s.length <= 2000$
• s는 소문자 영단어로만 이루어져 있다.

---

풀이

• 우리가 찾아야 하는 부분 문자열은 길이가 k 이상인 회문이어야 한다.
• 하지만 반환해야 하는 값은 회문의 길이가 아니라, 서로 겹치지 않게 선택할 수 있는 회문의 개수이다.
• 따라서 긴 회문 하나를 찾는 것보다, 가능한 한 짧은 회문을 여러 개 선택하는 것이 유리하다.
• 그렇다면 길이가 k인 회문만 찾으면 충분할까?

• 회문의 양 끝 문자를 하나씩 제거하면, 남은 문자열 역시 회문이다.
• 즉 길이가 k + 2 이상인 회문은 양 끝을 계속 제거하면서 더 짧은 회문으로 만들 수 있다.
• 다만 회문의 길이는 한 번에 2씩 줄어들기 때문에 홀수 길이와 짝수 길이의 성질은 유지된다.
• 따라서 길이가 k 이상인 회문이 존재한다면, 그 안에는 반드시 길이가 k 또는 k + 1인 회문이 존재한다.
• 결국 모든 길이의 회문을 검사할 필요 없이, 각 위치에서 k와 k + 1 길이의 회문만 검사하면 된다.
• 둘 다 선택 가능한 경우에는 더 짧은 k 길이의 회문이 이후 문자열을 더 많이 남길 수 있지만, 실제 선택은 DP가 두 경우를 비교해서 결정한다.

코드

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        N = len(s)

        def check(left: int, right: int) -> bool:
            if left >= N or right >= N:
                return 0

            while left < right:
                if s[left] != s[right]:
                    return 0

                left, right = left + 1, right - 1

            return 1

        @cache
        def dp(index: int) -> int:
            if index >= N:
                return 0

            ans = dp(index + 1)

            if check(index, index + k - 1):
                ans = max(ans, 1 + dp(index + k))

            if check(index, index + k):
                ans = max(ans, 1 + dp(index + k + 1))

            return ans

        return dp(0)