Leetcode 3223. Minimum Length of String After Operations

2024년 1월 13일 (월)
Leetcode daily problem

3223. Minimum Length of String After Operations

https://leetcode.com/problems/minimum-length-of-string-after-operations/description/?envType=daily-question&envId=2025-01-13

문제를 ...하지 못해서 문제를 이해하는데 30분이 걸려벌인..

문자열 s가 주어졌을 때 문자열에서 다음과 같은 과정을 여러 번 수행할 수 있다

• 문자열 인덱스 i를 선택해서, 해당 인덱스 i의 기준으로 왼쪽에 같은 문자가 하나 이상 있고, 오른쪽에 같은 문자가 하나 이상 있어야 한다.
• 인덱스 i에서 가장 가까운 왼쪽에 있는 동일한 문자를 삭제하고 인덱스 i에서 가장 가까운 오른쪽에 있는 동일한 문자를 삭제한다.

이러한 과정에서 최종적으로 얻을 수 있는 최소 길이를 반환한다.

Solution

문자열 빈도

문자열 카운트를 세서 문자가 3회 이상 등장할 경우 해당 카운트를 2만큼 줄이면서 문제를 해결한다.

Code

class Solution:
    def minimumLength(self, s: str) -> int:
        freq = [0] * 26
        
        for c in s:
            freq[ord(c)-ord('a')] +=1
        
        for i in range(26):
            while freq[i] >=3:
                freq[i]-=2
        
        return sum(freq)

Complexicity

시간 복잡도

문자열을 한 번 쓰윽 순회하면서 문자열 빈도수를 파악하므로 O(n)
문자열의 개수인 26번 순회는 O(26)이라 O(1)

while 문에서 freq[i]가 3 이상일 때 실행되는데, 최대 26까지 있을 수 있어서 한 번의 순회당 2번 이하로만 수행되어 O(26) 이라 O(1)

전체 시간 복잡도는 O(n) 이다.

공간 복잡도

freq 배열은 크기가 26인 정수 배열이고, 크기는 고정되어 있고 O(1) 이라고 볼 수 있다.