题目
对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。
给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。
测试样例："aabcb",5
返回：3
思路
设字符串为s，当前位置i, dp[i-1]表示以i-1位置为结尾的最长无重复子串子串（以下简称为子串）的开始位置。并设置一个map,记录字符s[i]上一次出现的位置lastOcc。
PS：dp[i-1]在图片中表示为pre,此处使用dp[i-1]只是为了方便理解动态规划的思想，优化之后可以省去。
如果lastOcc<dp[i-1], dp[i]=dp[i-1];
来自牛客网，有删改
如果lastOcc>=dp[i-1],dp[i]=lastOcc+1;
Paste_Image.png
综上 ：dp[i]=Math.max(dp[i-1],lastOcc+1);
所以我们可以得出以每一个位置为终点的子串的起始位置,即可以得出以每个位置为终点的每个子串的长度，从中取最大值即可。
程序代码
用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;
}
}
