- 不定長的 Sliding Window 套 pattern
class IWindow {
public:
virtual void add(int num) = 0;
virtual void erase(int num) = 0;
virtual bool check() = 0;
virtual ~IWindow() {}
};
class Window: public IWindow {
private:
int _maxCost;
int _curr = 0;
public:
Window(int maxCost): _maxCost(maxCost) {}
void add(int num) override {
_curr += num;
}
void erase(int num) override {
_curr -= num;
}
bool check() override {
return _curr > _maxCost;
}
};
class Solution {
private:
unique_ptr<IWindow> _w;
public:
int equalSubstring(string s, string t, int maxCost) {
auto nums = [&](int i) -> int {
return abs(s[i] - t[i]);
};
_w = make_unique<Window>(maxCost);
int n = s.size(), left = 0, right = 0;
int res = 0;
while (right < n) {
_w->add(nums(right++));
while (_w->check()) _w->erase(nums(left++));
res = max(res, right - left);
}
return res;
}
};
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int curr = 0;
int n = s.size(), left = 0, right = 0;
int res = 0;
while (right < n) {
curr += abs(s[right] - t[right]);
right++;
while (curr > maxCost) {
curr -= abs(s[left] - t[left]);
left++;
}
res = max(res, right - left);
}
return res;
}
};