【LeetCode】3. 无重复字符的最长子串

题目

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

示例

输入: "abcabcbb"

输出: 3

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

解题

一、暴力解法

循环每种可能出现的情况（二重循环）
取每组情况最大长度值

public int LengthOfLongestSubstring(string s)
{
    if (string.IsNullOrEmpty(s)) return 0;

    if (s.Length == 1) return 1;

    int max = 0;
    var hashSet = new HashSet<char>();

    for (int i = 0; i < s.Length; i++)
    {
        hashSet.Clear();
        hashSet.Add(s[i]);

        for (int j = i + 1; j < s.Length; j++)
        {
            if (!hashSet.Add(s[j])) break;
        }
        max = hashSet.Count > max ? hashSet.Count : max;
    }
    return max;
}

View Code

二、分治法

将字符串分成两段str[0 ~ n/2] 和 str[n/2 + 1 ~ n]，最长子串存在以下3种情况
- 最长子串在str[0 ~ n/2]　　　　
- 最长子串在str[n/2+1 ~n]
- 最长子串跨越在 str[0 ~ n/2] 和 str[n/2 +1 ~ n]
情况1，2，就取对应的字符串最长长度就可以　　
情况3，若最长子串跨越两个字符串，必定是左右两个字符串重复出现的字符中间，所以左边扫描遇到重复停止，右边扫描遇到重复停止

public int LengthOfLongestSubstring(string s)
{
    if (string.IsNullOrEmpty(s)) return 0;

    if (s.Length == 1) return 1;

    int lMax = 0, rMax = 0;
    int mid = s.Length / 2;
    var dic = new Dictionary<char, int>();

    for (int right = 0, left = 0; right < s.Length; right++)
    {
        if (dic.ContainsKey(s[right]))
        {
            left = Math.Max(dic[s[right]], left);  //标记左边为上一次位置，Max防止后面出现之前的
            if (left > mid) break;
        }

        lMax = Math.Max(lMax, right - left + 1);     //计算当前窗体长度（right - left + 1) 取最大值
        dic[s[right]] = right + 1;                 //更新当前字符位置
    }

    if (lMax >= s.Length) return lMax;
    dic.Clear();

    for (int right = s.Length - 1, left = s.Length - 1; left >= 0; left--)
    {
        if (dic.ContainsKey(s[left]))
        {
            right = Math.Min(dic[s[left]], right);  //标记左边为上一次位置，Max防止后面出现之前的
            if (right < mid) break;
        }

        rMax = Math.Max(rMax, right - left + 1);     //计算当前窗体长度（right - left + 1) 取最大值
        dic[s[left]] = left - 1;                     //更新当前字符位置

    }
    return Math.Max(lMax, rMax);
}

View Code

三、滑动窗口

　　什么是滑动窗口？在队列每次进入元素时判断是否符合条件，若不符合移除队尾数据，直到符合条件加入元素。

HashSet存放字符
定义两个变量（i，j)从字符串头开始扫描
- 若str[j] 不存在hashSet里，添加str[j]并且j++（向右移动）
- 若str[j] 存在hastSet里，移除str[i]并且i++　（向左移动）

public int LengthOfLongestSubstring(string s)
{
    if (string.IsNullOrEmpty(s)) return 0;

    if (s.Length == 1) return s.Length;

    var hashSet = new HashSet<char>();
    int i = 0, j = 0, max = 0;

    while (i < s.Length && j < s.Length)
    {
        if (hashSet.Contains(s[j]))
        {
            hashSet.Remove(s[i++]);
        }
        else
        {
            hashSet.Add(s[j++]);
            max = Math.Max(hashSet.Count, max);
        }
    }
    return max;
}

View Code

四、优化滑动窗口

　　从上面可以知道，每次查找到存在的字符从开始移除，最坏的情况是每个字符都会访问两次，上面算法时间复杂度：O(2n)

循环过程记录字符的位置
遇到相同字符时，直接移动左边标记到上次字符出现位置
过程中记录每组最大长度（右边 - 左边）

public int LengthOfLongestSubstring(string s)
{
    if (string.IsNullOrEmpty(s)) return 0;

    if (s.Length == 1) return s.Length;

    int max = 0;
    var dic = new Dictionary<char, int>();
    for (int right = 0, left = 0; right < s.Length; right++)
    {
        if (dic.ContainsKey(s[right]))
        {
            left = Math.Max(dic[s[right]], left);  //标记左边为上一次位置，Max防止后面出现之前的
        }

        max = Math.Max(max, right - left + 1);     //计算当前窗体长度（right - left + 1) 取最大值
        dic[s[right]] = right + 1;                 //更新当前字符位置
    }
    return max;
}

View Code

　　性能情况：方法一 < 方法二 < 方法三 < 方法四　　

来源：力扣（LeetCode）

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