Leet Code Daily 2024-05-28 - Get Equal Substrings With Budget
Solution
Linear scan.
Code
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
auto cost = [&s, &t](const int i) { return abs(s[i] - t[i]); };
int n = s.length(), ans = 0;
for (int i = 0, j = 0, currentCost = 0; i < n;) {
while (j < n && currentCost + cost(j) <= maxCost) {
currentCost += cost(j++);
}
ans = max(ans, j - i);
currentCost -= cost(i++);
}
return ans;
}
};