2021-01-31 之 最长不含重复字符的子字符串

题目地址

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

题目描述

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

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

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

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

这里提供一个最简单的思路， 滑动窗口算法

/**
 * @Author: vividzcs
 * @Date: 2021/1/31 8:42 下午
 */
public class LengthOfLongestSubstring {
    public static void main(String[] args) {
        String str = "tmmzuxt";
        int len = getMaxSubstringV3(str);
        System.out.println(len);
    }

    private static int getMaxSubstring(String str) {
        // 空或空字符串 字串长度为0
        if (str == null || str.length() ==0) {
            return 0;
        }
        // 长度为1 直接返回1
        if (str.length() == 1) {
            return 1;
        }
        // 只要不为空， 最大长度至少为1
        int max = 1;
        // 存储这个窗口的字符， 判断是否重复
        Set<Character> set = null;
        for (int i=0; i<str.length(); i++) {
            // 窗口起始位置
            set = new HashSet<>();
            set.add(str.charAt(i));
            for (int j=i+1; j <str.length(); j++) {
                // 不断扩大窗口， 如果有重复字符， 往前移
                if (set.contains(str.charAt(j))) {
                    break;
                }
                set.add(str.charAt(j));
                // 取当前最大长度和当前计算的长度的最大值
                max = Math.max(max, set.size());
            }
        }
        return max;
    }
    private static int getMaxSubstringV2(String str) {
        // 空或空字符串 字串长度为0
        if (str == null || str.length() ==0) {
            return 0;
        }
        // 长度为1 直接返回1
        if (str.length() == 1) {
            return 1;
        }
        // 只要不为空， 最大长度至少为1
        int max = 1;
        // 存储这个窗口的字符， 判断是否重复, 窗口是start到i
        int[] chars = new int[128];
        chars[str.charAt(0)] = 1;
        int start = 0;
        for (int i=1; i<str.length(); i++) {
            // 记录当前字符出现的次数
            char currentChar = str.charAt(i);
            chars[currentChar]++;
            //<=计算长度， 否则有重复， 需要右移
            if (chars[currentChar]>1) {
                // 一直右移， 把左边淘汰掉的字符出现次数减掉， 直到没有重复
                while (chars[currentChar] > 1) {
                    // 有重复字符串， 窗口右移直到没有重复字符
                    chars[str.charAt(start)]--;
                    start++;
                }
                // 这种情况窗口并没有扩大，不用计算大小
                continue;
            }
            // start到i即使窗口大小即最小无重复字串长度
            max = Math.max(max, i - start +1);
        }
        return max;
    }

    private static int getMaxSubstringV3(String str) {
        // 空或空字符串 字串长度为0
        if (str == null || str.length() ==0) {
            return 0;
        }
        // 长度为1 直接返回1
        if (str.length() == 1) {
            return 1;
        }
        // 只要不为空， 最大长度至少为1
        int max = 1;
        // 存储这个窗口的字符， 判断是否重复, 窗口是start到i
        Map<Character, Integer> map = new HashMap<>();
        int start = 0;
        for (int i=0; i<str.length(); i++) {
            // 记录当前字符出现的次数
            char currentChar = str.charAt(i);
            if (map.containsKey(currentChar)) {
                // 右移窗口到重复字符的后面个index，
                // map还有窗口外的值，但窗口外的值的index一定小于当前窗口开始位置（窗口左已经右移了）
                start = Math.max(start, map.get(currentChar) + 1);
                // 这里不能continue, 因为map里有窗口外的字符， 误进来如果continue会损失当前长度
            }
            map.put(currentChar, i);
            max = Math.max(max, i - start + 1);
        }
        return max;
    }
}