[LeetCode] 1763. Longest Nice Substring

- Problem

1763. Longest Nice Substring

문제에서의 nice는 주어진 문자열 s에서 임의의 문자가 소문자, 대문자 모두 존재할 때를 말한다.

이 문제는 s의 substring 중, 모든 문자가 nice를 만족하는 최장 길이 substring을 찾는 문제이다.

풀이 방식은 다음과 같다.

1. 전체 문자열 s의 임의의 문자 가 nice하지 않은 경우, 해당 문자를 기준으로 앞뒤로 문자열을 자른다.
   • 예를 들어, abcdABD일 경우, c의 대문자인 C는 존재하지 않기에 not nice한 문자이다. 반면에 a, A, b, B, c, C는 모두 존재하기에 nice한 문자이다.

2. 예시 abcdABD에서 c는 not nice한 경우이기에, 앞뒤인 ab와 dABD를 1번의 방식으로 다시 진행한다.

3. 최적의 답이 나올 때까지, 1과 2를 반복하다보면 Longest Nice Substring을 찾을 수 있다.

즉, 이 문제는 주어진 문제를 작은 문제로 분할하여 해결하는 분할 정복(divide and conquer)으로 접근해서 풀 수 있다.

- 내 풀이

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if not s: return ""
        
        set_string = set(s)
        
        for i, v in enumerate(s):
            if v.swapcase() not in set_string:
                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)
        
        else:
            return s

- 결과

분할 정복 문제는 풀 때마다 뚝배기가 너무 아리다.