Given a string, please find out the length of the longest substring that does not contain duplicate characters.

Example 1:

Type: "abcabcbb"
Output: 3
Explanation: because the longest substring without repeating characters is "abc", its length is 3.

Example 2:

Enter: "bbbbb"
Output: 1
Explanation: because the longest substring without repeating characters is "b", its length is 1.

1. Violent cracking

package leetcode;

import java.util.HashSet;

public class Demo2 {

	public static int LengthOfLongestSubstring(String str)
    {
        int resLength = 0;
        int strLength = str.length();
        HashSet<String> hashSet = new HashSet<String>();
        for (int i = 0; i < strLength; i++)
        {
            for (int j = i + 1; j < strLength; j++)
            {
                //All substrings of str can be determined here

            	String strChildren = str.substring(j, j+1);
                if (hashSet.contains(strChildren))
                {
                    break;
                }
                else
                {
                    hashSet.add(strChildren);
                }
               
            }
        }
        return resLength; 
    }
	public static void main(String[] args) {
		
		System.out.println(Demo2.LengthOfLongestSubstring("ababedf"));
	}

}

2. Big guy solution

Sliding window. By using HashSet as the sliding window, we can use the time of O(1) to check whether the character is in the current substring. Sliding window is a common abstract concept in array / String problems. A window is usually a set of elements defined by the start and end indexes in an array / string, i.e., [i, j) (left closed, right open). Sliding window is a window that can "slide" two boundaries in one direction. For example, if we slide [I, J] 1 element to the right, it will become [i+1, j+1) (left closed, right open).

Return to our question, we use the HashSet to store the characters in the current window [i, j) (initially j = - i). Then we slide the index j to the right, and if it's not in the HashSet, we'll continue to slide j. Until s[j] already exists in the HashSet. At this point, the longest substring we find without repeating characters will start with index i. If we do this for all i's, we can get the answer.

2.1 code implementation

public static int LengthOfLongestSubstring3(String str)
	 {
	     int resLength = 0;
	     int strLength = str.length();
	     int i = 0, j = 0;
	     HashSet<String> hashSet = new HashSet<String>();
	 
	     while (i < strLength && j < strLength)
	     {
	    	 String oneStrJ = str.substring(j,j+1);
	         if (!hashSet.contains(oneStrJ))
	         {
	             hashSet.add(oneStrJ);
	             j++;
	             resLength = Math.max(resLength,j-i);
	         }
	         else
	         {
	        	 String oneStrI = str.substring(i, i+1);
	             hashSet.remove(oneStrI);
	             i++;
	         }
	     }
	     return resLength;
	 }

2.2 code implementation:

The element of fast pointer j is not repeated, update max, mark the fast pointer j element in the hash table as appear, move j backward;
The element of fast pointer j is repeated, and the slow pointer moves backward. At this time, the mark of slow pointer i element in the hash table is cleared. At this time, it doesn't care who repeats. All elements before repeating elements should be removed.

	public static int lengthOfLongestSubstring(String s) {
        int []hash = new int [500];
        int max = 0;
        int i = 0, j = 0;

        while (i < s.length() && j <s.length() ) {
            if(hash[s.charAt(j)] == 0) {
                hash[s.charAt(j)] = 1;
                j++;
                max = (j - i) > max ? (j - i) : max;
            } else {
                hash[s.charAt(i)] = 0;
                i++;
            }  
        }
        return max; 
    }