[LeetCode] 3. Longest Substring Without Repeating Characters

class Window {
public:
    virtual void add(int num) = 0;
    virtual void erase(int num) = 0;
    virtual bool find(int num) = 0;
    virtual ~Window() {}
};

class Bucket : public Window {
private:c
    int _bucketSize;
    int _valueDiff;
    int index(int num) {
        return num < 0
            ? (num - _valueDiff) / _bucketSize
            : num / _bucketSize;
    }
    unordered_map<int,int> _map;
public:
    Bucket(int valueDiff): _valueDiff(valueDiff), _bucketSize(valueDiff + 1) {}
    void add(int num) override {
        int idx = index(num);
        _map[idx] = num;
    }
    void erase(int num) override {
        int idx = index(num);
        _map.erase(idx);
    }
    bool find(int num) override {
        int idx = index(num);
        return _map.count(idx) ||
            (_map.count(idx-1) && num - _map[idx-1] <= _valueDiff) ||
            (_map.count(idx+1) && _map[idx+1] - num <= _valueDiff);
    }
};

class Solution {
private:
    unique_ptr<Window> _w;
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        int n = nums.size();
        int k = indexDiff + 1;
        _w = make_unique<Bucket>(valueDiff);

        for (int i = 0; i < k && i < n; i++) {
            if (_w->find(nums[i])) return true;
            _w->add(nums[i]);
        }
        for (int i = k; i < n; i++) {
            _w->erase(nums[i-k]);
            if (_w->find(nums[i])) return true;
            _w->add(nums[i]);
        }
        return false;
    }
};

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        unordered_map<int,int> map;
        k++;
        for (int i = 0; i < n; i++) {
            int idxin = nums[i] / (t+1);
            if (nums[i] < 0) idxin--;
            if (i >= k) {
                int idxout = nums[i-k] / (t+1);
                if (nums[i-k] < 0) idxout--;
                map.erase(idxout); 
            }
            if (map.count(idxin) ||
            (map.count(idxin-1) && nums[i] - map[idxin-1] <= t) ||
            (map.count(idxin+1) && map[idxin+1] - nums[i] <= t)) return true;
            map[idxin] = nums[i];
        }
        return false;
    }
};