3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

英文题目

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

题目大意

给一个字符串,求最长的不重复子串。

解题思路

Solution1

直接遍历,想到重复,利用MAP保存字符出现的记录并维护一个滑动窗口
同时,只要和子串的第一个重复就是算是重复的,所以只需要判断第一个就可以。可以建立一个256位大小的整型数,因为ASCII表共能表示256个字符。

//    维护一个滑动窗口依次向右扩张
func lengthOfLongestSubstring(s string) int {
    res, left := 0, -1
    m := make(map[int]int)

    for i := 0; i < len(s); i++ {
        //    当前字符存在MAP中且位置位于滑动窗口内
        if _, ok := m[int(s[i])]; ok && m[int(s[i])] > left {
            //    移动滑动窗口的做边界到当前字符上次出现的位置
            left = m[int(s[i])]
        }
        //    当前字符并未出现,滑动窗口向右扩张
        m[int(s[i])] = i
        res = max(res, i-left)
    }

    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
//    数组版本
func lengthOfLongestSubstring(s string) int {
    allChar, res, left := [256]int{}, 0, -1

    for i := 0; i < 256; i++ {
        allChar[i] = -1
    }

    for i := 0; i < len(s); i++ {
        left = max(left, allChar[s[i]])
        allChar[s[i]] = i
        res = max(res, i-left)
    }
    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

Complexity Analysis

  • 时间复杂度:O(n).
  • 空间复杂度:O(n).

结语

如果你同我一样热爱数据结构、算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:awesome-golang-leetcode


  TOC