[LeetCode] 1208. Get Equal Substrings Within Budget

https://leetcode.com/problems/get-equal-substrings-within-budget/description/

leetcode - Get Equal Substrings Within Budget

문제 유형 : 문자열 처리, 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

You are given two strings s and t of the same length and an integer maxCost.

You want to change s to t. Changing the ith character of s to ith character of t costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of the characters).

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost. If there is no substring from s that can be changed to its corresponding substring from t, return 0.

 

같은 길이의 두 문자열 s와 t가 주어진다. maxCost 정수도 주어진다.

s를 t로 바꾸고 싶다.

s의 i번째 문자를 t의 i번째 문자로 바꾸는데 두 문자의 아스키 코드 차이만큼의 비용이 든다.

maxCost만큼 최대 사용하여 t와 같아질 수 있는 s의 부분문자열의 최대길이를 구해라.

 

풀이

슬라이딩 윈도우를 이용해 풀 수 있다.

left, right을 만든 뒤, right를 늘려가면서 cost를 누적시킨다. 만약 cost가 maxCost보다 커지면, cost가 maxCost보다 큰동안 left를 늘려가면서 윈도우의 범위를 좁힌다.

부분문자열의 길이를 업데이트하면서 값을 업데이트한다.

 

코드

C++

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.size();
        int ans = 0;
        int left = 0;
        int cost = 0;

        for(int right = 0; right < n; right++) {
            cost += abs(s[right] - t[right]);
            while(cost > maxCost) {
                cost -= abs(s[left] - t[left]);
                left++;
            }

            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};