1208. Get Equal Substrings Within Budget

문제

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

• s 문자열을 t로 바꿀 때 비용(ASCII 코드의 차이)이 maxCost를 만족하는 subArray의 최대 길이를 구하는 문제

풀이

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int cost = 0;
        int answer = 0;
        int lt = 0;
        for(int rt = 0; rt < s.length(); rt++) {
            char a = s.charAt(rt);
            char b = t.charAt(rt);
            cost += Math.abs(a - b);
            
            while(cost > maxCost) {
                cost -= Math.abs(s.charAt(lt) - t.charAt(lt));
                lt++;
            }
            answer = Math.max(answer, rt - lt + 1);
        }
        return answer;
        
    }
}

• subString의 최대 길이를 구해야하므로, 가능한 모든 subString를 O(N)으로 탐색
  -> Sliding Window 사용
• rt를 1씩 늘려가면서, cost를 구하고, cost가 maxCost를 넘는다면 lt++를 해주면서 범위 축소
  범위가 축소되면 그만큼 cost도 다시 계산!
• cost > maxCost가 아니게 됐을 때, subString의 조건을 만족하므로 answer를 갱신
  
  이런식으로 슬라이딩 윈도우가 가변길이로 움직이면서, 모든 가능한 subString를 탐색한다.
  

• lt가 총 N만큼 탐색 + rt도 총 N만큼 탐색 => O(N)의 시간복잡도를 가짐