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;
}