LeetCode-3 无重复的最长子串

忘是亡心i 2023-10-03 21:36 29阅读 0赞

#### 问题描述 ####

给定一个字符串 s，请你找出其中不含有重复字符的 **最长子串** 的长度。

> 示例 1:  
> 输入: s = “abcabcbb”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 `3`。

#### 动态规划思路 ####

##### 状态定义 #####

定义一个一维`dp`数组，`dp[i+1]`其含义为以下标`i`结尾的无重复子串长度。

##### 状态转移逻辑 #####

如果没有遇到重复的字符：`dp[i+1] = dp[i] + 1`。那么问题来了怎么处理判断重复的逻辑呢？根据小标从头遍历到当前，显然时间复杂度度太高，我们可以定义一个存储元素和其下标的HashMap来判断重复。  
如果遇到了重复字符：`dp[i+1] = i-map.get(char(i))`。`i-map.get(char(i))`为当前坐标减去上次出现的坐标。但是没考虑到`[map.get(char(i), i]`这个区间内出现重复子串的情况。比如`"abba"`、`"abbb"`。为此`dp[i+1]`需要取`dp[i]+1`和`i-map.get(char(i))`之间的最小值。即  
`dp[i+1] = min(dp[i]+1, i-map.get(char(i)))`。

##### 初始值及特殊情况 #####

`dp`数组全局赋初值`0`。返回值`res`需要一直更新取他与`dp[i+1]`间的最大值，因为问题求的是全局无重复的最长子串大小。串长度为`0`，就返回`0`。

#### 代码 ####

public static int lengthOfLongestSubstring(String s) {
        
            if (s.length()==0) return 0;
            int res = 1;
            int[] dp = new int[s.length()+1];
            HashMap<Character, Integer> map = new HashMap<>();
            char[] c = s.toCharArray();
            for (int i = 0; i < s.length(); i++) {
        
                if(!map.containsKey(c[i])){
        
                    dp[i+1] = dp[i]+1;
                }else{
        
                    dp[i+1] = Math.min(dp[i]+1, i-map.get(c[i]));
                }
                map.put(c[i], i);
                res = Math.max(res, dp[i+1]);
            }
            return res;
        }