[2024] day 66. Leetcode 1750. Minimum Length of String After Deleting Similar Ends

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 5일 (화)
Leetcode daily problem

1750. Minimum Length of String After Deleting Similar Ends

https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends/description/

Problem

'a', 'b', 'c' 문자로만 구성된 문자열 s가 주어질 때,
아래의 알고리즘에 따라 작업을 반복해서 수행한다.
(1) 문자열 's'에서 모두 동일한 문자로 이루어진 접두사를 선택한다.
(2) 문자열 's'에서 모두 동일한 문자로 이루어진 덥미사를 선택한다.
(3) 접두사와 접미사는 어떤 인덱스에서도 겹치지 않아야 한다.
(4) 접두사와 접미사의 문자들은 같아야 한다.
(5) 선택한 접두사와 접미사를 모두 삭제한다.

위와 같은 작업을 수행한 후의 's'의 최소 길이를 반환한다.

Solution

two pointer

해당 문제는 두 개의 포인터를 사용해서 문자열의 양 끝에서부터 비교하여 제거하는 방식으로 동작시킨다.
양 끝에서부터 비교해가면서 같은 문자일 경우 접두사와 접미사가 만나기 전까지 문자열을 양 끝에서 한 글자씩 제거해 나간 후에, 남은 문자열의 길이를 반환하면 된다.

여기서 example3에서 보듯이 주어진 문자열 s = 'aabccabba' 인 경우,
접두사가 'aa' 이고 접미사가 'a'여도 같은 문자열로 구성되어 있으므로 접두사를 'aa', 접미사를 'a'로 해서 앞뒤 'aa', 'a'를 제거할 수 있다.

그래서 양 끝 포인터를 좁혀나가는 과정에서, 앞쪽기준에서 +1, 뒤쪽기준에서 -1 씩 이동해나가면서 같은 문자열로 구성되어 있는지 확인하는 로직도 필요하다.

더이상 제거가 어려운 경우 오른쪽 포인터에서 왼쪽 포인터를 빼주고 +1을 해주어 최종 문자열의 길이를 산정하여 반환한다.

Code

class Solution:
    def minimumLength(self, s: str) -> int:
        left, right = 0, len(s)-1

        while left < right and s[left] == s[right]:
            while left < right and s[left] == s[left+1]:
                left +=1
            while left < right and s[right] == s[right-1]:
                right -=1

            left +=1
            right -=1

        return max(0, right-left+1)

Complexicity

시간 복잡도

주어진 문자열을 양 끝에서부터 비교하고 제거하므로 입력 문자열에 비례하는 O(n)의 시간복잡도이다.

공간 복잡도

추가적인 공간을 사용하지 않고 상수 변수만 사용하므로 공간복잡도는 O(1) 이다.