1208. Get Equal Substrings Within Budget - Medium

前往題目

想法

• 把string按照ascii排序
• 雙sliding window把結果找出來

思路

我的想法太多餘了，其實就是簡單的sliding window

1. sliding window
2. 每次循環更新當前總和
3. 超過maxCost就移動左指針
4. 更新結果

Code

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int l = 0;
        int res = 0;
        int curCost = 0;
        
        // Sliding window, keep moving right pointer
        for (int r = 0; r < s.length(); ++r) {
            // Update current cost
            curCost += Math.abs(s.charAt(r) - t.charAt(r));
            
            // Move left pointer until valid
            while (l <= r && curCost > maxCost) {
                curCost -= Math.abs(s.charAt(l) - t.charAt(l));
                ++l;
            }

            // Update if possible
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}