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

// O(n^3)

// consider all substrings one by one and check for each substring
// whether it contains all unique characters or not. There will be
// n*(n+1)/2 substrings. Whether a substring contains all unique
// characters or not can be checked in linear time by scanning it from
// left to right and keeping a map of visited characters.

// Time Complexity: O(n^3) since we are processing n^2 substrings with
// maximum length n.

int longestUniqueSubsttr(string str)
{
    auto areDistinct = [](string str, int from, int to)
    { 
        vector<bool> visited(26);
        for (int i = from; i <= to; i++) {
            if (visited[str[i] - 'a'] == true)
                return false;
            visited[str[i] - 'a'] = true;
        }
        return true;
    };
    
    int result = 0;
    for (int i = 0; i < (int)str.size(); i++)
        for (int j = i; j < (int)str.size(); j++)
            if (areDistinct(str, i, j))
                result = max(result, j - i + 1);
    return result;
}

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;
}