#include <bits/stdc++.h>

using namespace std;

// Problem 3. Longest Substring Without Repeating Characters
// Medium

// Given a string s, find the length of the longest substring without
// repeating characters.

class Solution {
public:
    int forLeet(string s) 
    {
        if (s.size() == 0) return 0;

        // set to keep track of non-repeating substr
        set<char> chars;
        
        chars.insert(s[0]);

        int maxSubstr = 0;
        int windowStart = 0;

        // linear time O(1)
        for (size_t idx = 1; idx < s.size(); idx++)
        {            
            if (chars.count(s[idx]) == 0)
            {
                // char not found, insert
                chars.insert(s[idx]);
            }
            else // found repeating char
            {
                maxSubstr = max(maxSubstr, (int)chars.size());

                // if prev char is repeating slide window starting at
                // current char
                if (s[idx] == s[idx - 1])
                {
                   chars.clear();
                   windowStart = idx;
                }
                
                //chars.insert(s[idx]);

                // move window
                else // (s[idx] != s[idx - 1])
                {
                    while (s[windowStart] != s[idx])
                    {
                        chars.erase(s[windowStart++]);
                    }
                    windowStart++;
                }
            }
        }

        maxSubstr = max(maxSubstr, (int)chars.size());        
        
        return maxSubstr;        
    }
    
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) return 0;
        
        set<char> chars;
        
        // vector to illustrate current window
        vector<char> charV;
        
        chars.insert(s[0]);
        charV.push_back(s[0]);

        int windowStart = 0;        

        auto print = [](int pos, const vector<char>& charV, const set<char>& chars)
        {
            cout << "winPos: " << pos << " charV: "; for (auto& i: charV) { cout << i; }; cout << " chars: "; for (auto& i: chars) { cout << i; }; cout << endl;
        };
        
        cout << "init charV: "; print(windowStart, charV, chars);        
        
        int maxSubstr = 0;

        for (size_t idx = 1; idx < s.size(); idx++)
        {            
            if (chars.count(s[idx]) == 0)
            {
                chars.insert(s[idx]);
                charV.push_back(s[idx]);
                cout << "next idx: " << idx << " char: " << s[idx] << endl;
                print(windowStart, charV, chars);

            }
            else
            {
                bool consecutiveRepeat = (s[idx] == s[idx-1] ? true : false);
                string ss = (consecutiveRepeat == true ? "' consecutive repeating" : "' repeat");
                
                cout << "next idx: " << idx << " char: '" << s[idx] << ss << endl;
                print(windowStart, charV, chars);
                
                maxSubstr = max(maxSubstr, (int)chars.size());
                cout << "maxSubstr: " << maxSubstr << endl;

                // reset window to current idx for consecutive repeating characters
                if (consecutiveRepeat)
                {
                    chars.clear();
                    charV.clear();
                    windowStart = idx;
                }     
                
                chars.insert(s[idx]);
                charV.push_back(s[idx]);

                // move window
                if (!consecutiveRepeat)
                {                    
                    while (s[windowStart] != s[idx])
                    {
                        chars.erase(s[windowStart++]);
                        charV.erase(charV.begin());
                    }
                    windowStart++;
                    charV.erase(charV.begin());
                }
                
                cout << "move window: "; print(windowStart, charV, chars);
            }
        }

        maxSubstr = max(maxSubstr, (int)chars.size());
        
        return maxSubstr;
    }
};

int main()
{
    vector<tuple<string, string, int>> testCases =
    {
//  string           substr   longestSubstr   
//  --------         ------   -------------
    {"abcabcbb",      "abc",      3},
    {"bbbbb",         "b"  ,      1},
    {"pwwkew",        "wke",      3}, 
    {"abcabcdabcde",  "abcde",    5},
    {"",              "",         0},
    {"dvdf",          "vdf",      3},
    {"anviaj",        "nviaj",    5},
    {"geeksforgeeks", "eksforg",  7},
    {"ckilbkd",       "ckilb",    5},
    };

    Solution s;

    for (auto& tc: testCases)
    {
        int len = s.lengthOfLongestSubstring(get<0>(tc));
        cout << "str: " << get<0>(tc) << " actual: " << len
             << " expected: " << get<2>(tc) << " substr: " << get<1>(tc) << endl;
        cout << (len == get<2>(tc) ? "passed" : "failed") << endl;        
        cout << "---------------\n";        
    }
    

    
    return 0;    
}