/**
 * Given a string, find the length of the longest substring without repeating characters. 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. 
 */

/**
 * 给定一个字符串，找字符中的最大非重复子串
 */
/**
 * 做题必须先想到所有可能出现的情况
 */
package LongestSubstringWithoutRepeatingCharacters;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
	public static int lengthOfLongestSubstring(String s) {
		//字符串输入不合法
		if(s == null) {
			return 0;
		}
		
		int max_unique_char_size = 0;
		int start = 0;	//当前位置
		//访问标记，记录访问过的字符和位置
		Map<Character,Integer> map = new HashMap<>(s.length());
		
		for(int i=0;i<s.length();i++) {
			char ch = s.charAt(i);
			if(map.containsKey(ch) && map.get(ch) >= start) {
				start = map.get(ch)+1;
			}else {
				max_unique_char_size = Math.max(max_unique_char_size,i-start+1);
			}
			map.put(ch,i);
		}
		
		return max_unique_char_size;
	}
	
	public static void main(String[] args) {
		String s = "abcabcbb";
		System.out.print(lengthOfLongestSubstring(s));
	}
}