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

in with 0 comment

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

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

示例 1:

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

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

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  1. 暴力破解时间复杂度过高,使用动态规划,状态转移方程:
    1. dp[j - 1] < j - i,说明 s[j] 字符在区间 dp[j - 1] 外,dp[j] = dp[j - 1] + 1
    2. dp[j - 1] >= j - i,说明 s[j] 字符在区间 dp[j - 1] 内,dp[j] = j - i\

该逻辑可使用三种方式写逻辑:

  1. 使用 dic 记录每个节点最后出现的位置,时间复杂度 O(n)
  2. 使用变量 i 移动位置,如果出现和 j 位置相等的情况,即可得出左边界,时间复杂度 O(n ^ 2)
  3. 使用 dic 记录每个元素最后出现的位置,根据上轮左指针 i 和 dic[s[j]] ,每轮更新左边界 i ,保证区间 [i + 1, j] 内无重复字符且最大,最后取上轮 res 和本轮双指针区间 [i + 1,j] 的宽度(即 j - i )中的最大值。

代码

解法一

class Solution {
    public int lengthOfLongestSubstring(String s) {
        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;
            res = Math.max(tmp, res);
        }
        return res;
    }
}
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0, tmp = 0;
        for (int j = 0; j < s.length(); j++) {
            int i = j - 1;
            while (i >= 0 && s.charAt(i) != s.charAt(j)) i--;
            tmp = tmp < j - i ? tmp + 1 : j - i;
            res = Math.max(tmp, res);
        }
        return res;
    }
}
class Solution {
    public int lengthOfLongestSubstring(String s) {
        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)));
            dic.put(s.charAt(j), j);
            res = Math.max(res, j - i);
        }
        return res;
    }
}