参考资料：左程云算法课

3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.Example 1:Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.Constraints:0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

思路：
首先，以str[i]为例，计算 局部最优解 以str[i]为结尾的无重复字符的最长子串的长度。然后，遍历字符串，即i取0，1，…, n-1，取局部最优解的最大值，得到全局最优解。
具体地，求 以str[i]为结尾的无重复字符的最长子串的长度，可以使用动态规划的方法。
dp[i]表示 以str[i]为结尾的无重复字符的最长子串的长度。
以str[i]为结尾的无重复字符的子串不停地向左扩，直到扩不动了为止。扩不动的原因有两个：
第一，碰到了与str[i]相同的字符；
第二，碰到了dp[i-1]的局部最优解对应的开头的前一个位置，也就是令dp[i-1]扩不动的地方。
上面两个位置取最大，就是 令 以str[i]为结尾的无重复字符的子串 向左扩不下去的地方。此时，可以求得dp[i]。

一些实现细节：
使用数组map记录，遍历到i字符时，之前的所有字符最近出现过的位置。
注意：“还没出现过”的位置不能使用默认值0，而是指定为-1.
这是因为，‘0’ 已经有自己的含义了，如map['a']=0表示字符’a’最近一次出现是在0位置。

// 写法1：有dp表的动态规划public int lengthOfLongestSubstring3(String s) {if(s==null || s.length()==0){return 0;}char[] chs = s.toCharArray();int n=chs.length;int[] dp = new int[n];dp[0]=1;int[] map = new int[256];for(int i=0;i<256;i++){map[i]=-1;}map[chs[0]]=0;int res=1;for(int i=1;i<n;i++){dp[i] = i-Math.max(map[chs[i]],i-1-dp[i-1]);// Math.max(map[chs[i]],i-1-dp[i-1])是 局部最优开头的前一位的坐标if(dp[i]>res){res=dp[i];}map[chs[i]]=i;}return res;}// 写法2：省去了dp表，只使用有限几个变量，因为dp[i]在dp表中只依赖dp[i-1]public int lengthOfLongestSubstring(String s) {if(s==null || s.length()==0){return 0;}char[] str = s.toCharArray();int n = str.length;int[] map = new int[256];for(int i=0;i<n;i++){map[str[i]]=-1;}int pre = -1;int cur=1;int res=1;map[str[0]]=0;for(int i=1;i<n;i++){pre = Math.max(pre,map[str[i]]);cur = i-pre;res = cur>res?cur:res;map[str[i]]=i;}return res;}// 写法2： 和上面一样的写法，这里有些注释，可供参考public int lengthOfLongestSubstring2(String s) {if(s==null || s.length()==0){return 0;}char[] str = s.toCharArray();int[] map=new int[256];// <char,position>for(int i=0;i<256;i++){map[i]=-1; // 因为‘0’已经有含义了，它表示 the first index// 所以我们选择另外一种数字表示 “还没出现过”}// LSs who ends up with [i], //  pre ： dp[i-1]'s previous index of its locally optimal startint pre = -1;int cur = 0;// local optint ans=cur;// global optfor(int i=0;i<str.length;i++){pre = Math.max(pre,map[str[i]]);cur = i-pre;map[str[i]]=i;ans = Math.max(ans,cur);}return ans;}