算法：无重复字符的最长子串

题目

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

示例一

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

示例二

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

示例三

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

示例四

输入: s = ""
输出: 0

提示

0 <= s.length <= 5 * 10^4

s由英文字母、数字、符号和空格组成

思路

创建数组记录字符出现过的位置。定义start指针记录最长字串开始的索引，当符号出现过时，start指针指向上一次出现的位置的下一位，但要注意判断start指针只能一直往后移，如果符号出现的索引位置比start小，则start位置不变。

实现

public static int lengthOfLongestSubstring(String s) {
    // 记录字符上一次出现的位置
    // 英文字母、数字、符号和空格，不考虑 & 等中文符号。
    int[] last = new int[128];
    for (int i = 0; i < 128; i++) {
        last[i] = -1;
    }

    int longestCount = 0;
    int start = 0; // 开始位置指针
    for (int i = 0; i < s.length(); i++) {
        int charAscii = s.charAt(i);
        int index = last[charAscii];// 字符上一次出现的位置，没出现过就是-1
        if (index != -1) {// 如果出现过，开始位置指针指向上一次出现的位置的下一位
            // 如：dvdf，第一次d出现在第0位，所以最长子串开始计算的索引就是0，但当第二个d出现了，所以有重复了，最长子串的计算计算的索引也要往后移一位，从v开始计算。
            // 如：abba，第一次a出现在第0位，但当第二个d出现时，索引往后移一位就要比较原先记录的start即b的下一位索引大还是a的下一位索引大。
            // start = index + 1; // 要防止 abba 情况，故 index + 1 与之前记录的 start 比大小
            start = Math.max(start, index + 1);
        }
        longestCount = Math.max(longestCount, i - start + 1);
        last[charAscii] = i;
    }

    return longestCount;
}

LeetCode 原题地址

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters