3. 无重复字符的最长子串：

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

样例 1：

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

样例 2：

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

样例 3：

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

提示：

• 0 <= s.length <= 5 * 10⁴
• s 由英文字母、数字、符号和空格组成

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 官方题解使用滑动窗口，尝试从每个字符开始找无重复的最长子串。
• 而我们这里换一种方式，是判断到每个字符为止的无重复的最长子串。因为存储了每个字符的最后出现下标，所以不需要内层循环来滑动窗口，可以直接定位出子串的开始位置。

题解：

rust

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        // 存每个字符最后的下标
        let mut last = [-1; 128];
        // 子串下标的前一位
        let mut left = -1;
        // 结果
        let mut ans = 0;

        for (i, c) in s.chars().enumerate() {
            // 右移left
            left = left.max(last[c as usize]);
            // 修改字符最后下标
            last[c as usize] = i as i32;
            // 刷新结果
            ans = ans.max((i as i32) - left);
        }

        ans
    }
}

go

func lengthOfLongestSubstring(s string) int {
    // 存每个字符最后的下标
    last := make([]int, 128)
    for i := range last {
        last[i] = -1
    }
    // 子串下标的前一位
    left := -1
    // 结果
    ans := 0

    for i, c := range s {
        // 右移left
        if last[c] > left {
            left = last[c]
        }
        // 修改字符最后下标
        last[c] = i
        // 刷新结果
        if i-left > ans {
            ans = i - left
        }
    }

    return ans
}

c++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 存每个字符最后的下标
        int last[128];
        memset(last, -1, sizeof(int) * 128);

        int left = -1;
        int ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s[i];
            // 右移left
            left = max(left, last[c]);
            // 修改字符最后下标
            last[c] = i;
            // 刷新结果
            ans = max(ans, i - left);
        }

        return ans;
    }
};

c

int lengthOfLongestSubstring(char * s){
    // 存每个字符最后的下标
    int last[128];
    memset(last, -1, sizeof(int) * 128);

    int left = -1;
    int ans = 0;
    for (int i = 0; s[i] > 0; ++i) {
        char c = s[i];
        // 右移left
        left = fmax(left, last[c]);
        // 修改字符最后下标
        last[c] = i;
        // 刷新结果
        ans = fmax(ans, i - left);
    }

    return ans;
}

python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 存每个字符最后的下标
        last = [-1] * 128
        # 子串下标的前一位
        left = -1
        # 结果
        ans = 0
        for i in range(len(s)):
            c = ord(s[i])
            # 右移left
            if last[c] > left:
                left = last[c]
            # 修改字符最后下标
            last[c] = i
            # 刷新结果
            if i - left > ans:
                ans = i - left
        return ans

java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~