파이썬으로 같은 문자가 연속되는 가장 긴 부분 문자열의 길이 찾기

문자열 s가 주어졌을 때, 동일한 문자가 연속으로 나타나는 가장 긴 부분 문자열(서브스트링)의 길이를 구하는 문제입니다.

예를 들어 입력이 "abbbaccabbbba"라면, 'b'가 네 번 연속으로 등장하는 구간이 있으므로 출력 결과는 4가 됩니다.

해결 접근 방법

이 문제는 문자열을 한 번만 순회하면서 인접한 두 문자를 비교하는 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

• 문자열 s의 길이가 0이라면 0을 반환합니다.
• 문자열 끝에 공백 한 문자를 추가합니다. 이렇게 하면 마지막 문자 그룹도 비교 로직에서 자연스럽게 처리됩니다.
• 최종 카운터 변수 ct와 현재 연속 길이를 저장하는 임시 변수 tem을 각각 1로 초기화합니다.
• 인덱스 0부터 문자열 길이 - 2까지 반복하며 다음을 수행합니다.
  • s[i]와 s[i+1]이 같다면 tem을 1 증가시킵니다.
  • 다르다면 ct에 tem과 ct 중 더 큰 값을 저장하고, tem을 1로 초기화합니다.
• 반복이 끝나면 ct를 반환합니다. 이것이 곧 가장 긴 연속 문자 블록의 길이입니다.

구현 예제

아래 파이썬 코드를 통해 실제 동작을 확인할 수 있습니다.

class Solution:
    def solve(self, s):
        if len(s)==0:
            return 0
        s+=' '
        ct=1
        tem=1
        for i in range(len(s)-1):
            if s[i]==s[i+1]:
                tem+=1
            else:
                ct=max(tem,ct)
                tem=1
        return ct
ob = Solution()
print(ob.solve("abbbaccabbbba"))

입력

"abbbaccabbbba"

출력

4

시간 복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 따라서 매우 긴 문자열에 대해서도 효율적으로 동작합니다.