Question

from lintcode

Given a string, find the length of the longest substring without repeating characters.

Example
For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1.

Idea

The key to give an optimal solution is to realize this:

A string has order, so you should not exhaust all character combinations. You just have to consider combinations which follow the array order.

Second, you have to deduce the lemma as follows:

If a substring contains duplicated letters, which is invalid, any string that contains this substring must be invalid as well.

So, you can start from a start position, initially 0, and try to extend the letters to construct substrings until you encounter duplicates, in which case, you shrink from the start position by incrementing it until the shrunk string contains no duplicates. By that time, you can start the extending process again.

The point to optimize is this: You usually want to maintain a Set to record distinct letters among string[i to j]. You don't have to reconstruct the whole Set when you shrink the range by incrementing i. Just simply remove the character at position i from the Set when you increment it.

import java.util.*;  

public class Solution {
    /*
     * @param s: a string
     * @return: an integer
     */
    public int lengthOfLongestSubstring(String ss) {
        int i = 0;
        int j = 0;
        int longest = 0;
        int current = 0;
        Set<Character> visited = initSet();
        
        char[] s = ss.toCharArray();
        for(i = 0; i < s.length; i++){
            while(j < s.length){
              
              if(visited.contains(s[j])){
                break;
              }
              
              visited.add((s[j++]));
            }
            
            current = j - i;
            longest = Math.max(current, longest);            
            

            visited.remove(s[i]);
        }
        
        return longest;
    }
    
    public Set<Character> initSet(){
        return new HashSet<Character>();
    }
}