#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.

#define NO_OF_CHARS 256

void print(int wIdx, int res, string str, int j, const vector<int>& v) 
{
    cout << "v: ";
    for (size_t i = 0; i < v.size(); i++ )
    {
        if (v.at(i) != -1 )
            cout << "['" << char(i) << "'" << i <<"," << v.at(i) << "], ";
    }
    cout << endl;
    cout << "wIdx: " << wIdx << " res: " << res << " j: " << j << " str[j]: '" << str[j] << "'(" << int(str[j]) << ") lastIndex[str[j]]: " << v[str[j]] << endl;
}

// Ending index ( j ) : We consider current index as ending index.
//
// Starting index ( i ) : It is same as previous window if current
//   character was not present in the previous window. To check if the
//   current character was present in the previous window or not, we
//   store last index of every character in an array lastIndex[]. If
//   lastIndex[str[j]] + 1 is more than previous start, then we update
//   the start index i. Else we keep same i.
     
int longestUniqueSubsttr(string str)
{
    int n = str.size();
 
    int res = 0; // result
 
    // last index of all characters is initialized
    // as -1
    vector<int> lastIndex(NO_OF_CHARS, -1);
    print(0, 0, str, 0, lastIndex);
    cout << "----------" << endl;
 
    // Initialize start of current window
    int i = 0;
 
    // Move end of current window
    for (int j = 0; j < n; j++) {
 
        // Find the last index of str[j]
        // Update i (starting index of current window)
        // as maximum of current value of i and last
        // index plus 1
        i = max(i, lastIndex[str[j]] + 1);
 
        // Update result if we get a larger window
        res = max(res, j - i + 1);
 
        // Update last index of j.
        lastIndex[str[j]] = j;
        print(i, res, str, j, lastIndex);
    }
    return res;
}
 
// Driver code
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},
    };
    
    for (auto& tc: testCases)
    {
        cout << get<0>(tc) << endl;        
        int len = longestUniqueSubsttr(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;
}