题解 | JAVA #最长不含重复字符的子字符串# [P1-T2]

遍历每个字符，记录每个字符最近一次出现的位置。

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