[2024] day 150. leetcode 1208. Get Equal Substrings Within Budget

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

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

1208. Get Equal Substrings Within Budget

https://leetcode.com/problems/get-equal-substrings-within-budget/?envType=daily-question&envId=2024-05-28

Problem

두 개의 문자열 s와 t가 주어졌을 때, 두 문자열을 같은 문자열로 만드는 데 필요한 비용이 주어진 예산 maxCost를 초과하지 않도록 하는 가장 긴 연속된 부분 문자열의 길이를 찾는 문제이다. 여기서 비용은 두 문자열의 각 문자의 차이에 해당한다.

Solution

Sliding Window

슬라이딩 윈도우 알고리즘을 사용하여 문자열 s와 t를 순회하면서, 두 포인터 start와 i를 이용해 윈도우를 유지한다.

문자열 s의 길이 n에 따라 n번 반복하는데,
루프 내부에서 현재의 비용을 계산하고 현재 비용이 maxCost 보다 크다면 윈도우의 시작위치를 오른쪽으로 이동하고 비용을 줄인다.

이러한 과정을 통해서 문자열의 문자를 한번씩 처리해 가능한 가장 긴 부분 문자열을 탐색한다.

Code

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        curCost, start = 0,0
        maxLen = 0
        
        for i in range(n):
            curCost += abs(ord(s[i]) - ord(t[i]))
            
            if curCost > maxCost:
                curCost -= abs(ord(s[start]) - ord(t[start]))
                start +=1
            
            maxLen = max(maxLen, i-start+1)
            
        
        return maxLen

Complexicity

시간 복잡도

주어진 문자열 s의 길이만큼 반복하면서 탐색하는 과정에서 내부의 while 문은 특정 상황에서 실행하는데, start 포인터와 i 포인터가 각각 n 번씩 이동할 수 있다.

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

공간 복잡도

추가 적인 데이터 구조를 사용하지 않으므로 공간복잡도는 O(1) 이다.