题目
对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。
给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。
思路
- DP思想：最优子结构、重复子问题
- Hash：存储上一个位置，辅助DP进行
答案
int longestSubstring(string A, int n) {
// 存储上一个重复字符的位置
int *lastPosition = new int[256];
for (int i = 0; i < 256; i++) {
lastPosition[i] = -1;
}
// 动态规划过程
int previous = -1;// 前一个的最长子串左节点位置
int current = 0;
int maxLength = 0;
for (int i = 0; i < n; i++) {
previous = max(previous, lastPosition[A[i]]);
current = i - previous;
maxLength = max(current, maxLength);
lastPosition[A[i]] = i;
}
return maxLength;
}
