파이썬으로 가장 긴 좋은(Nice) 부분 문자열 찾는 방법

문자열 s가 주어졌을 때, s 안에서 가장 긴 "좋은(nice)" 부분 문자열을 찾는 것이 목표입니다.

어떤 문자열이 "좋은(nice)" 문자열이 되려면, 해당 문자열에 포함된 모든 알파벳이 대문자와 소문자 양쪽 형태로 모두 나타나야 합니다. 조건을 만족하는 부분 문자열이 여러 개라면, 그중 가장 먼저 등장하는 것을 반환해야 합니다.

예를 들어 입력이 s = "ZbybBbz"라면 결과는 "bBb"입니다. 이 부분 문자열에는 소문자 b와 대문자 B가 함께 들어 있어 조건을 충족하기 때문입니다.

접근 방법

이 문제는 완전 탐색(brute force) 방식으로 해결할 수 있습니다. 모든 시작 위치 i에 대해 끝 위치 j를 하나씩 늘려가며 부분 문자열을 검사하고, 지금까지 등장한 대문자 집합(upper)과 소문자 집합(lower)이 동일해지는 순간을 찾습니다. 두 집합이 같다는 것은 부분 문자열 내 모든 문자가 대소문자 쌍을 이루고 있다는 의미입니다.

알고리즘 단계

cur_max := -1 (가장 긴 길이를 저장하는 변수)
res := 빈 문자열 (결과를 저장하는 변수)
i를 0부터 s의 길이까지 반복:
- c := s[i]
- upper := 새로운 집합 생성
- lower := 새로운 집합 생성
- c가 소문자이면 lower에 추가
- c가 대문자이면 소문자로 변환한 뒤 upper에 추가
- j를 i+1부터 s의 길이까지 반복:
  - c := s[j]
  - c가 소문자이면 lower에 추가
  - c가 대문자이면 소문자로 변환한 뒤 upper에 추가
  - upper == lower이면:
    - j - i > cur_max이면 cur_max := j-i로 갱신하고, res := s[i:j+1]로 갱신

res 반환

구현 예제

다음 코드를 통해 더 잘 이해할 수 있습니다.

예제 코드

def solve(s):
    cur_max= -1
    res=""
    for i in range(len(s)):
        c = s[i]
        upper = set()
        lower = set()
        if c.islower():
            lower.add(c)
        if c.isupper():
            upper.add(c.lower())
        for j in range(i+1,len(s)):
            c = s[j]
            if c.islower():
                lower.add(c)
            if c.isupper():
                upper.add(c.lower())
            if upper == lower:
                if j-i>cur_max:
                    cur_max = j-i
                    res = s[i:j+1]
    return res
s = "ZbybBbz"
print(solve(s))

입력

"ZbybBbz"

출력

bBb

핵심 포인트 정리

대소문자 통일 비교: 대문자는 항상 .lower()로 변환해 저장하므로, upper 집합과 lower 집합을 서로 직접 비교할 수 있습니다.
집합 비교의 의미: upper == lower가 참이라는 것은 부분 문자열에 등장한 모든 문자가 대문자·소문자 형태를 모두 갖추었다는 뜻입니다.
시간 복잡도: 이중 반복문 구조로 시간 복잡도는 O(n²) 수준이며, 길이가 짧거나 중간 정도인 문자열에 효율적으로 동작합니다.
최초 발견 우선: 엄격한(>) 비교를 사용하기 때문에 길이가 같은 후보가 여러 개일 때 가장 먼저 발견된, 즉 더 앞선 위치의 부분 문자열이 결과로 유지됩니다.