leetcode 1208. Get Equal Substrings Within Budget

Seawolf

1. You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.
   
2. 
   
3. You are also given an integer maxCost.
   
4. 
   
5. Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.
   
6. 
   
7. If there is no substring from s that can be changed to its corresponding substring from t, return 0.
   
8. 
   
9. 
   
10. 
    
11. Example 1:
    
12. 
    
13. Input: s = "abcd", t = "bcdf", maxCost = 3
    
14. Output: 3
    
15. Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.
    
16. Example 2:
    
17. 
    
18. Input: s = "abcd", t = "cdef", maxCost = 3
    
19. Output: 1
    
20. Explanation: Each character in s costs 2 to change to charactor in t, so the maximum length is 1.
    
21. Example 3:
    
22. 
    
23. Input: s = "abcd", t = "acde", maxCost = 0
    
24. Output: 1
    
25. Explanation: You can't make any change, so the maximum length is 1.
    
26. 
    
27. 
    
28. Constraints:
    
29. 
    
30. 1 <= s.length, t.length <= 10^5
    
31. 0 <= maxCost <= 10^6
    
32. s and t only contain lower case English letters.

复制代码

sliding window!

1. class Solution {
   
2.     public int equalSubstring(String s, String t, int k) {
   
3.         int i = 0, j;
   
4.         int n = s.length();
   
5.         for(j = 0; j<n ; j++){
   
6.             k -= Math.abs(s.charAt(j) - t.charAt(j));
   
7.             
   
8.             if(k < 0) k+= Math.abs(s.charAt(i) - t.charAt(i++));
   
9.         }
   
10.         
    
11.         return j - i;
    
12.     }
    
13. }

复制代码