//
// Created by wangxiaobo on 2020/6/26.
//
#include <utils.h>

// sliding window
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) {
            return 0;
        }
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(); i++) {
            while (lookup.find(s[i]) != lookup.end()) {
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
        }
        return maxStr;
    }

    int lengthOfLongestSubstring2(string s)
    {
        if(s.empty()) return 0;
        int map[128] = {0};
        const unsigned char* ptr_begin = (unsigned char*)s.c_str();
        const unsigned char* ptr = ptr_begin;
        const unsigned char* begin = ptr_begin;
        int max_length = 1;
        int begin_n = 1;
        map[*ptr++] = 1;

        while(*ptr){
            unsigned char c = *ptr;
            cout << "c=" << c << " begin_n=" << begin_n << endl;
            if(map[c] >= begin_n){
                max_length = max(max_length, (int)(ptr - begin));
                begin_n = map[c];
                begin = ptr_begin + begin_n;
                cout << "adjust windows" << endl;
                cout << "map[c]=" << map[c] << " begin_n=" << begin_n << " begin=" << begin << endl;
            }
            map[c] = ptr - ptr_begin + 1;
            ++ptr;
        }
        return max(max_length, (int)(ptr - begin));
    }
};

TEST(_0003, LongestSubstring) {
    Solution sln;
    ASSERT_EQ(sln.lengthOfLongestSubstring("abcabcbb"), 3);
    ASSERT_EQ(sln.lengthOfLongestSubstring("bbbbb"), 1);
    ASSERT_EQ(sln.lengthOfLongestSubstring("pwwkew"), 3);

    ASSERT_EQ(sln.lengthOfLongestSubstring2("abcabcbb"), 3);
}