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

int longestUniqueSubsttr(string str)
{
    // map to store the last positions of occurrence
    map<char, int> seen ;
    int maximum_length = 0;
    
    // Starting the initial point of window to index 0
    int start = 0;
 
    for(int index = 0; index < (int)str.size(); index++)
    {         
        // Checking if we have already seen the element or not
        if (seen.find(str.at(index)) != seen.end())
        {
            // If we have seen the char, move the start
            // pointer to position after the last occurrence
            start = max(start, seen[str.at(index)] + 1);
        }
 
        // Updating the last seen value of the character
        seen[str.at(index)] = index;
        
        maximum_length = max(maximum_length, index - start + 1);
    }
    
    return maximum_length;    
}
 
// 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)
    {
        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;
}