題目
對于一個字符串,請?jiān)O(shè)計(jì)一個高效算法，找到字符串的最長無重復(fù)字符的子串長度杯矩。
給定一個字符串A及它的長度n栈虚，請返回它的最長無重復(fù)字符子串長度。保證A中字符全部為小寫英文字符史隆，且長度小于等于500魂务。
測試樣例："aabcb",5
返回：3
思路
設(shè)字符串為s，當(dāng)前位置i, dp[i-1]表示以i-1位置為結(jié)尾的最長無重復(fù)子串子串（以下簡稱為子串）的開始位置。并設(shè)置一個map,記錄字符s[i]上一次出現(xiàn)的位置lastOcc粘姜。
PS：dp[i-1]在圖片中表示為pre,此處使用dp[i-1]只是為了方便理解動態(tài)規(guī)劃的思想鬓照，優(yōu)化之后可以省去。
如果lastOcc<dp[i-1], dp[i]=dp[i-1];
來自畔嗤В客網(wǎng)颖杏，有刪改
如果lastOcc>=dp[i-1],dp[i]=lastOcc+1;
Paste_Image.png
綜上 ：dp[i]=Math.max(dp[i-1],lastOcc+1);
所以我們可以得出以每一個位置為終點(diǎn)的子串的起始位置,即可以得出以每個位置為終點(diǎn)的每個子串的長度，從中取最大值即可坛芽。
程序代碼
用pre代替了dp[],如果還有錯誤或者不明白的地方請給我留言留储，謝謝。
import java.util.*;
public class DistinctSubstring {
public int longestSubstring(String A, int n) {
if(n<=1) return n;
int maxLen=0;
Map<Character,Integer>map=new HashMap<>();
char[] arr=A.toCharArray();
map.put(arr[0],0);
int pre=0;
Integer lastOcr=null;
for(int i=1;i<n;i++){
lastOcr=map.get(arr[i]);
if(lastOcr==null) lastOcr=-1;
pre=Math.max(lastOcr+1,pre);
maxLen=Math.max(i-pre+1,maxLen);
map.put(arr[i],i);
}
return maxLen;
}
}
