[Leetcode] 1208. Get Equal Substrings Within Budget - Python, Two Pointer, Sliding Window

접근

1. 투포인터
2. 슬라이딩 윈도우

길이가 같은 문자열 s에서 t로 변환할 때 maxCost 이하의 비용으로 변환 가능한 최대 부분문자열 길이를 구하는 문제이다. Cost를 maxCost 이하로 유지하며 투포인터로 부분문자열을 유지하면 될 듯하다. 이 때, 최대 길이를 구하는 문제이므로 고정 크기의 슬라이딩 윈도우가 조금 더 빠를 것이다.

풀이

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:

        curr_cost = left = 0
        
        for right in range(len(t)):

            curr_cost += abs(ord(s[right]) - ord(t[right]))

            if curr_cost > maxCost:
                curr_cost -= abs(ord(s[left]) - ord(t[left]))
                left += 1
        
        return right - left + 1