#include "s0003_longest_substring_without_repeating_characters.hpp"

int S0003::lengthOfLongestSubstring(std::string s) {
  // index_forward points to the frontmost element
  // index_backward points to the last repeated element
  //
  // for
  //    check if index_forward pointed element exists in hash map
  //            if exists, index_backward = max(index_backward, the index of
  //            this element)
  //    push
  //    index_forward += 1
  //    len = max(index_forward, index_backward)
  std::map<char, int> map;
  int index_backward{-1};
  int index_forward{0};
  int len{0};
  for (; index_forward < s.length(); index_forward++) {
    if (map.count(s[index_forward]) == 1) {
      index_backward = std::max(index_backward, map.at(s[index_forward]));
    }
    map[s[index_forward]] = index_forward;
    len = std::max(len, index_forward - index_backward);
  }
  return len;
}