leetcode-cn Daily Challenge on Feburary 5th, 2021.
Difficulty : Medium
Related Topics : Array、Sliding Window
You are given two strings
s
andt
of the same length. You want to changes
tot
. Changing thei
-th character ofs
toi
-th character oft
costs|s[i] - t[i]|
that is, the absolute difference between the ASCII values of the characters.You are also given an integer
maxCost
.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 tomaxCost
.If there is no substring from
s
that can be changed to its corresponding substring fromt
, return0
.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.
Input: s = "abcd", t = "cdef", maxCost = 3 Output: 1 Explanation: Each character in s costs 2 to change to charactor in t, so the maximum length is 1.
Input: s = "abcd", t = "acde", maxCost = 0 Output: 1 Explanation: You can't make any change, so the maximum length is 1.
1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s
andt
only contain lower case English letters.
- mine
- Java
Runtime: 4 ms, faster than 93.00%, Memory Usage: 39.2 MB, less than 64.56% of Java online submissions
public int equalSubstring(String s, String t, int maxCost) { int len = s.length(); int[] count = new int[len]; for (int i = 0; i < s.length(); i++) { count[i] = Math.abs(s.charAt(i) - t.charAt(i)); } int left = 0; int ans = 0; int cost = 0; for (int i = 0; i < len; i++) { cost += count[i]; while (cost > maxCost && left <= i) { cost -= count[left]; left++; } ans = Math.max(ans, i - left + 1); } return ans; }
- Java