[Leetcode] 1208. Get Equal Substrings Within Budget

문제

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.
 
Example 1:
Input: s = "abcd", t = "bcdf", maxCost = 3 Output: 3 Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.
Example 2:
Input: s = "abcd", t = "cdef", maxCost = 3 Output: 1 Explanation: Each character in s costs 2 to change to character in t, so the maximum length is 1.
Example 3:
Input: s = "abcd", t = "acde", maxCost = 0 Output: 1 Explanation: You cannot make any change, so the maximum length is 1.
 
Constraints:
1 <= s.length <= 105t.length == s.length0 <= maxCost <= 106s and t consist of only lowercase English letters.

 

풀이

 

어떤 컨디션에서 가장 짧거나 긴 substring을 구해야 하는 문제는 주로 sliding window 가 많이 쓰이는 것 같다. 

이번 문제도 sliding window 를 생각하면 쉽게 답을 찾을 수 있다.

(물론 나는 한번에 떠올리지 못했다.)

 

sum <= maxCost 일때, range를 늘리고; sum < maxCost 일때 range를 줄인다.

 

코드

int equalSubstring(char* s, char* t, int maxCost) {
    int sum = 0, max = 0;
    int left = 0;
    for(int right=0; s[right]; right++) {
        sum += abs(s[right] - t[right]);

        while(sum > maxCost) {
            sum -= abs(s[left] - t[left]);
            left++;
        }

       if(max < (right-left)+1) max = (right-left)+1;
    }
    return max;
}

 

코멘트: char for loop 일때 (int i=0; i<strlen(string); i++) 보다 (int i=0; string[i]; i++)가 훨씬 빠르다. 

 

애초에 strlen(string)이 사실은 밑의 코드를 계속 구하는거라 되도록 한번 variable에 저장하고 쓰는게 효율적이다....

size_t strlen(const char* str) {
    size_t len = 0;
    while (str[len] != '\0') {
        len++;
    }
    return len;
}