분할정복(divide_and_conquer) 기법 문제: Longest Nice Substring

• 문자열 s에서 “nice” 문자열을 찾고, 그중 가장 긴 하위 문자열(substring)을 반환하라.
• “nice” 문자열의 조건:문자열에 포함된 모든 문자는 해당 문자의 대문자와 소문자가 모두 포함되어야 함.
• 예: “aA”는 “nice”, “a”는 “nice”가 아님.
• 출력 조건:가장 긴 “nice” 문자열을 반환.
• 여러 개의 “nice” 문자열이 동일한 길이라면 가장 먼저 등장하는 문자열을 반환.
• “nice” 문자열이 없으면 빈 문자열 “” 반환.

---

• 문자열 s (길이 1 ≤ len(s) ≤ 100).
• 문자열 s는 영어 소문자와 대문자로만 구성됨.

---

• 가장 긴 “nice” 하위 문자열.

---

예제 1. 예제 1:

Input: s = "YazaAay"
Output: "aAa"
Explanation:
- "aAa"는 'A/a'의 대소문자가 모두 포함된 "nice" 문자열.
- "aAa"가 가장 긴 "nice" 하위 문자열이므로 반환.

2. 예제 2:

Input: s = "Bb"
Output: "Bb"
Explanation:
- "Bb"는 'B/b'가 모두 포함된 "nice" 문자열.
- 문자열 전체가 "nice" 하위 문자열이므로 반환.

3. 예제 3:

Input: s = "c"
Output: ""
Explanation:
- "c"는 대문자 'C'가 없으므로 "nice" 문자열이 아님.

---

• 문자열의 길이가 최대 100이므로, O(n^2) 또는 적절한 효율성을 가진 알고리즘을 사용해야 함.
• 대소문자 확인은 char.upper()와 char.lower()로 간단히 처리 가능.

---

• 각 문자에 대해 대소문자 쌍이 있는지 확인.
• 대소문자 쌍이 없는 경우 문자열을 분할하여 처리.
• 문자열을 반복적으로 나누어 “nice” 조건을 만족하는 가장 긴 문자열을 찾음.
• 문자열을 작은 단위로 나눌수록 효율적으로 문제를 해결 가능.
• 문자열 길이가 100이므로 재귀 기반의 분할 정복이 시간 제한 내에서 동작 가능.

---

슬라이딩 윈도우 방식으로 풀려고 해봤었음. **

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        n = len(s)

        small_set:set = {} # 소문자의 중복을 확인하기 위한 집합
        big_set: set = {} # 대문자의 중복을 확인하기 위한 집합
        
        nice_substr: str = "" # 결과 값(최대길이 나이스 문자열)

        left:int = 0 # 윈도우의 시작점
        for right in range(len(s)):
            if s[right] == s[right].isUpper():
                while s[right] not in small_set:
                  # ...

• 윈도우의 크기가 일정하거나, 연속적 데이터의 합/곱/최대/최소를 업데이트하는 경우.
• 각 단계에서 새로운 데이터가 들어오고, 오래된 데이터가 빠질 때 효율적으로 처리 가능한 경우.
• 각 문자에 대해 대소문자 쌍이 있는지 확인해야 하므로 윈도우가 업데이트될 때마다 모든 문자 세트를 재확인해야 합니다.
• “nice” 문자열의 조건은 윈도우 내 모든 문자가 대소문자 쌍으로 존재하는지에 따라 결정됩니다. 이는 윈도우의 변화를 효율적으로 추적하기 어렵게 만듭니다.

---

따라서 권장 접근법: 분할 정복 ** 이 문제는 분할 정복(Divide and Conquer)을 사용하여 해결하는 것이 더 적합합니다. 아래는 분할 정복을 사용하는 코드입니다:

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if len(s) = len(right) else right

        return s

---

• 기본 조건:문자열 길이가 2보다 작으면 “nice” 문자열이 될 수 없으므로 빈 문자열 반환.
• 분할 기준:현재 문자열의 문자 집합(char_set)을 만들고, 각 문자를 순회하며 해당 문자의 대소문자 쌍이 있는지 확인.
• 대소문자 쌍이 없다면 그 문자를 기준으로 문자열을 분할.
• 재귀적으로 처리:분할된 두 부분 문자열에 대해 재귀적으로 longestNiceSubstring을 호출.
• 두 부분 중 더 긴 문자열을 반환.
• 모든 문자가 조건을 만족하면:현재 문자열이 “nice” 문자열이므로 반환.

---

테스트

solution = Solution()

print(solution.longestNiceSubstring("YazaAay"))  # 출력: "aAa"
print(solution.longestNiceSubstring("Bb"))       # 출력: "Bb"
print(solution.longestNiceSubstring("c"))        # 출력: ""
print(solution.longestNiceSubstring("dDzeE"))    # 출력: "dD"

---

• 최악의 경우, 문자열을 반씩 분할하며 탐색하므로 시간 복잡도는 O(n^2) 입니다.