字串和子序列

港控/mmm° 2022-12-03 09:48 14阅读 0赞

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

# 最长不含重复字符的子串 #

[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/][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]

*  动态规划

![202009031041242.png_pic_center][]

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

[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]: 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/
[202009031041242.png_pic_center]: /images/20221123/45d8596f12ea4632ba2e007e0be6b394.png