[LeetCode] 1208. Get Equal Substrings Within Budget

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;
    }
};