子串：连续的子字符串子序列：不连续子字符串

最长不含重复字符的子串

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/

动态规划

public class test_0901_1 { public static void main(String[] args) { Scanner input = new Scanner(System.in); String s = input.nextLine(); Map<Character, Integer> dic = new HashMap<>(); int res = 0, tmp = 0; for (int j = 0; j < s.length(); j++) { int i = dic.getOrDefault(s.charAt(j), -1); dic.put(s.charAt(j), j); tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j] res = Math.max(res, tmp); // max(dp[j - 1], dp[j]) } System.out.println(res); } } 双指针 public class test_0901_1 { public static void main(String[] args) { Scanner input = new Scanner(System.in); String s = input.nextLine(); Map<Character, Integer> dic = new HashMap<>(); int i = -1, res = 0; for (int j = 0; j < s.length(); j++) { if (dic.containsKey(s.charAt(j))) i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i dic.put(s.charAt(j), j); // 哈希表记录 res = Math.max(res, j - i); // 更新结果 } System.out.println(res); } }