题解 | JAVA #最长不含重复字符的子字符串# [P1-T2]
最长不含重复字符的子字符串
http://www.nowcoder.com/practice/48d2ff79b8564c40a50fa79f9d5fa9c7
遍历每个字符，记录每个字符最近一次出现的位置。
dp[i]: length of longest substring without duplicates ending at i
dp[i] = {
dp[i-1] + 1 // if dp[i-1] does not contiain chars[i]
i - j // j is the max index of chars[i] in dp[i-1]
}
import java.util.*;
public class Solution {
public int lengthOfLongestSubstring (String s) {
Map<Character, Integer> charIdx = new HashMap<>();
int dp = 0;
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int lastIdx_c = charIdx.getOrDefault(c, -1);
// first idx in dp[i-1]: (i-1) - dp[i-1] + 1 = i-dp[i-1]
if (lastIdx_c < i - dp) // dp[i-1] does not contain c
dp++;
else // dp[i-1] contains c
dp = i - lastIdx_c;
maxLen = Math.max(maxLen, dp);
charIdx.put(c, i);
}
return maxLen;
}
}
DP是真的烦 文章被收录于专栏
只是为了把DP的题集中一下方便自己复习
