[LeetCode]Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring withoutrepeating characters.Example 1:Input: “abcabcbb” Output: 3 Explanation: The answer is “abc”, withthe length of 3. Example 2:Input: “bbbbb” Output: 1 Explanation: The answer is “b”, with thelength of 1. Example 3:Input: “pwwkew” Output: 3 Explanation: The answer is “wke”, with thelength of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.对xxx串，它的最长不重复子串情况可以完全由xx可以决定，确认是dp问题确定状态转移方程，定义dp[i]为与当前串构成不重复串的indexdp[i]=Math.max(dp[i-1],count[s.charAt(i-1)]+1);public int lengthOfLongestSubstring(String s) { int ret=0; int l=s.length(); int[] dp=new int[l+1]; int[] count=new int[128]; for(int i=1;i<=l;i++){ dp[i]=Math.max(dp[i-1],count[s.charAt(i-1)]+1); ret=Math.max(ret,i+1-dp[i]); count[s.charAt(i-1)]=i; } return ret; }