/**********************************************************
** 3.Longest Substring Without Repeating Characters
** Given a string, find the length of the longest substring without repeating characters.
**
** Examples:
** Given "abcabcbb", the answer is "abc", which the length is 3.
** Given "bbbbb", the answer is "b", with the length of 1.
** Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
**********************************************************/
#include <string>
#include <iostream>
#include <map>

using namespace std;

int lengthOfLongestSubstring(string s) {
    int longestLen = 0;
    int lastRepeatPos = -1;
    map<char, int> matchCharacters;

    for (int i=0; i<s.size(); ++i) {
        if (matchCharacters.find(s[i]) != matchCharacters.end() && lastRepeatPos < matchCharacters[s[i]]) {
            lastRepeatPos = matchCharacters[s[i]];
        } 

        if (i-lastRepeatPos > longestLen) {
            longestLen = i-lastRepeatPos;
        }

        matchCharacters[s[i]] = i;
    } 

    return longestLen;    
}

//-----example-----
int main(int arc, char ** argv) {
    string s = "abcabcbb";
    cout << s << ":" << lengthOfLongestSubstring(s) << endl;

    s = "bbbbb";
    cout << s << ":" << lengthOfLongestSubstring(s) << endl;

    s = "pwwkew";
    cout << s << ":" << lengthOfLongestSubstring(s) << endl;

    return 0;
}

//-----output-----
//abcabcbb:3
//bbbbb:1
//pwwkew:3