LeetCode 3 – Longest Substring Without Repeated Characters

Solution to LeetCode Longest Substring Without Repeated Characters problem.

The idea is that last[i] is the last occurence of the letter (with ascii code) i, or \(-1\) if it hasn’t appeared yet. ‘cur_len’ is the length of the current sequence we are considering.

First, process the first character and setup all the variables accordingly. Then, for every other character:

• Check if it has already appeared before. If not, then no problem, increment cur_len and mark it as seen.
• Otherwise, there are two cases:
  • We check if the last occurence of char \(i\) is part of the sequence we are currently considering. If not, we are fine, increment cur_len and continue
  • Otherwise, we have a new contiguous substring without repeated characters. We update the maximum, and update cur_len

public int lengthOfLongestSubstring(String s) {
  if(s.length() == 0) return 0;
  char[] C = s.toCharArray();

  int[] last = new int[150];
  for(int i = 0; i < last.length; i++) last[i] = -1;

  last[C[0]] = 0;

  int max_len = 1;
  int cur_len = 1;

  for(int i = 1; i < C.length; i++){
    int lastIndex = last[C[i]];

    if(lastIndex == -1 || i - lastIndex > cur_len){
      cur_len++;
    }
    else{
      max_len = Math.max(max_len, cur_len);
      cur_len = i - lastIndex;
    }

    last[C[i]] = i;
  }
  return Math.max(max_len, cur_len);
}