1208. Get Equal Substrings Within Budget
Medium
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 i^{th}
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 <= 10^{5}
t.length == s.length
0 <= maxCost <= 10^{6}

s
andt
consist of only lowercase English letters.
Solution:
class Solution {
/**
* @param String $s
* @param String $t
* @param Integer $maxCost
* @return Integer
*/
function equalSubstring($s, $t, $maxCost) {
$j = 0;
for ($i = 0; $i < strlen($s); ++$i) {
$maxCost = abs(ord($s[$i])  ord($t[$i]));
if ($maxCost < 0)
$maxCost += abs(ord($s[$j])  ord($t[$j++]));
}
return strlen($s)  $j;
}
}
Contact Links
Top comments (0)