剑指 Offer 48. 最长不含重复字符的子字符串

本问题对应的 leetcode 原文链接:剑指 Offer 48. 最长不含重复字符的子字符串
对应打卡任务:【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串

问题描述

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

提示:

  • s.length <= 40000

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    // public int lengthOfLongestSubstring(String s) {
    //     if(s == null || s.length() <= 0){
    //         return 0;
    //     }
    //     // 优化 => 单个变量
    //     Map<Character,Integer> map = new HashMap<>();
    //     int[] dp = new int[s.length()];
    //     dp[0] = 1;
    //     map.put(s.charAt(0), 0);
    //     int res = 1;
    //     for(int i = 1; i < s.length(); i++){
    //         if(!map.containsKey(s.charAt(i))){
    //             dp[i] = dp[i-1] + 1;
    //         }else{
    //             int k = map.get(s.charAt(i));
    //             dp[i] = i - k <= dp[i-1] ? i - k : dp[i-1] + 1;
    //         }
    //         res = Math.max(res, dp[i]);
    //         map.put(s.charAt(i), i);
    //     }

    //     return res;
    // }

    // 优化版本
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() <= 0){
            return 0;
        }
        // 优化 => 单个变量
        Map<Character,Integer> map = new HashMap<>();
        //int[] dp = new int[s.length()];
        int a = 1;
        map.put(s.charAt(0), 0);
        int res = 1;
        for(int i = 1; i < s.length(); i++){
            if(!map.containsKey(s.charAt(i))){
                a = a + 1;// 就是没有刷新 a 之前,a表示dp[i-1]
            }else{
                int k = map.get(s.charAt(i));
                a = i - k <= a ? i - k : a + 1;
            }
            res = Math.max(res, a);
            map.put(s.charAt(i), i);
        }

        return res;
        // 时间On,空间On
    }
}

时间复杂度:O(n)
空间复杂度:O(n)

发表回复

后才能评论