Longest Substring Without Repeating Characters

Given a string, find the longest substring without any repeating characters and return the length of it. The input string is guaranteed to be not null.

For example, the longest substring without repeating letters for "bcdfbd" is "bcdf", we should return 4 in this case.

High level

hashTable to track chars seen and their last seen index

for each char in string

if not in HT:

curmax += 1

update globalmax

add char, index into HT

if is in HT:

get index of char

curmax = current index - index of repeated char

for 0 to index of repeated char: HT.remove(String.charAt(i))

public class Solution {
  public int longest(String input) {

    Map<Character, Integer> ht = new HashMap<>();
    int globalMax = 0;
    int curMax = 0;
    for (int i = 0; i < input.length(); i++){
      Character cur = input.charAt(i);
      if (!ht.containsKey(cur)){
        curMax += 1;
        globalMax = Math.max(globalMax, curMax);
        ht.put(cur, i);
      } else {
        int prevIndex = ht.get(cur);
        int left = i - curMax; //left end of cur substring
        while(left <= prevIndex){
          Character removeChar = input.charAt(left);
          ht.remove(removeChar);
          left += 1;
        }
        ht.put(cur, i);
        curMax = i - prevIndex;
      }
    }

    return globalMax;
  }
}