LeetCode-面试题48-最长不含重复字符的子字符串

题目

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

示例1：

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

示例2：

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

示例3：

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

解题思路

方法1、DP+哈希表：

设置右边界为j，左边界为i

• 当字串左边没有相同的字符时，dp[j] = dp[j-1]+1
• 当dp[j-1]<j-i，说明字符在dp[j-1]区间之外，如acbr，对于acb而言下一个字符r不是重复的字符，其在dp[j-1]之外，所以dp[j] = dp[j-1]+1
• 当dp[j-1]>=j-i，说明字符在dp[j-1]区间之中，含有重复字符，则dp[j]的左边界由第一次出现的重复字符的位置觉得，dp[j]=j-i

第一二种情况可以合并为一个，由于返回值取dp列表最大值，可以借助dp变量，存储dp[j]，每轮更新res

节省原本需要dp列表的空间

方法2、双指针+哈希表：

按照顺序遍历字符串，同时计算子串的长度，当到达相同的字符时候，自然希望子串的起始位置变成重复的位置。

而下一次子串的长度则=计算下一次碰到重复字符的位置end到上一次碰到重复字符位置start的差

那么如何去知道前面是否有重复的字符？

如果不使用hash表，就需要从最开始遍历到末尾end进行判断，这样时间复杂度太高。

所以这里采用hash表的方式存储每一个字符最后出现的位置，以便于快速找到上一次start的位置，由于遍历从0开始，所以将start初始化为-1，表示第一个位置长度为1，最后取最大的字串长度

Java代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> dict = new HashMap<>();
        int res = 0,dp = 0;
        for(int j=0;j<s.length();j++){
            int i = dict.containsKey(s.charAt(j))?dict.get(s.charAt(j)):-1; // 获取索引
            dict.put(s.charAt(j),j); // 更新hash
            // dp[j-1] < j-i时，dp[j-1]+1
            // dp[j-1] > j-i时，j-i
            dp = dp<j-i?dp+1:j-i;
            res = Math.max(res,dp); // max(dp[j-1],dp[j])
        }
        return res;
    }
}

Python代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start,res= -1,0
        positionMap = {}
        for end in range(len(s)):
            if s[end] in positionMap:
                start = max(positionMap[s[end]],start)
            positionMap[s[end]] = end
            res = max(res,end-start)
        return res