无重复字符的最长子串

CategoryDifficultyLikesDislikes
algorithmsMedium (34.87%)3872-

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

示例 1:

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

示例 2:

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

示例 3:

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

Discussion | Solution

读题

从给定字符串中查找不重复的最长子字符串的最大长度

反面教材

正如读题所说,那就暴力遍历所有子串判断排除重复项最后取最长的吧

public class Solution
{
  public int LengthOfLongestSubstring(string s)
  {
    string nowStr = "";
    int maxRes = 0;
    //遍历字符
    for (int startIndex = 0; startIndex < s.Length; startIndex++)
    {
      int lengthMax = s.Length - startIndex;
      //遍历每个char开头的所有长度的字符串
      for (int i = 1; i <= lengthMax; i++)
      {
        //小于当前最长的可以不遍历
        if (i <= maxRes)
        {
          continue;
        }
        //当前字符串
        nowStr = s.Substring(startIndex, i);
        bool repeat = isRepeat(nowStr);
        if (!repeat)
        {
          //没有重复,记录长度
          maxRes = nowStr.Length;
        }

      }
    }
    return maxRes;
  }

  public bool isRepeat(string s)
  {
    //计算字符串中所有字符的索引,第一个索引和最后一个索引值不一样表示有重复
    foreach (var item in s)
    {
      int fstIndex = s.IndexOf(item);
      int lastIndex = s.LastIndexOf(item);
      if (fstIndex != lastIndex)
      {
        return true;
      }
    }
    return false;
  }
}


这里是个反面教材,缺乏思考偷懒只会增加加班时长!
无脑遍历,时间复杂度太高,对于输入值过长且复杂的情况,性能严重下降
反例:当给定字符串非常长非常爆炸的时候,执行时间也非常爆炸!

时间复杂度: O(n^n^n)【要查找长度为n的字符串中的所有子串,每个子串还要遍历每个字符检查是否重复,极其爆炸】

优化策略

用正常人类思维考虑程序问题:
abcbda如何判断结果是cbda,长度为4呢?

  • 从头开始数,不重复的话,记录长度

此时我们数到"abc"=3

  • 遇到重复"b"

两个"b"之间的字母肯定不重复,那我们取出来,再拼上末尾的"b"
得到"c"+"b"="cb"

  • 得到的"cb"有没有破纪录呢?

"cb"=2 最大是3,没有破纪录,那还是3

  • 继续数,上次到第二个"b",该"d"了

重复1234,最后得到"cbda"=4
4>3,破纪录了,记录为4

  • 数完啦!

最后的记录是4!
卧槽!人脑实在是太聪明了


这就是传说中的,滑动窗口算法!

正确解法

public class Solution
{
  public int LengthOfLongestSubstring(string s)
  {
    //特殊处理,空字符串直接返回
    if (string.IsNullOrEmpty(s))
    {
      return 0;
    }
    //非空字符串最小返回值也是1
    int maxRes = 1;
    //当前窗口
    List<char> nowWindow = new List<char>();
    foreach (var nowChar in s)
    {
      //遍历字符串的每个字符,窗口中存在,则抛弃前一个字符以前的所有
      //如 字符串abcb 当前abc 遇到第2个b 则窗口abc->c(去掉b及b以前的所有)
      if (nowWindow.Contains(nowChar))
      {
        nowWindow.RemoveRange(0, nowWindow.IndexOf(nowChar) + 1);
      }
      //再加上b到末尾成为窗口成为cb
      nowWindow.Add(nowChar);
      //当前窗口是否大于历史最大尺寸,大于则刷新纪录
      if (nowWindow.Count > maxRes)
      {
        maxRes = nowWindow.Count;
      }
    }
    return maxRes;
  }
}

结果

  • 987/987 cases passed (92 ms)
  • Your runtime beats 93.12 % of csharp submissions
  • Your memory usage beats 40 % of csharp submissions (25 MB)

思考

  • 可以看到速度很快,空间占用还是不如人意。
  • 可否使用Dictionary 利用key不重复的结构特性实现优化?
  • 空间占用不行是因为使用了List,可否通过记录窗口起始index及结束index,计算子串重复更改窗口始末index位置仅使用几个int记录索引完成计算,从而减少空间占用呢?

膜拜大佬

如果大佬们有更好的解法,不如评论分享赐教~
我的Leetcode解题代码库

本文作者:Author:     文章标题:【LeetCode】3.无重复字符的最长子串
本文地址:https://traceless.site/index.php/archives/32/     
版权说明:若无注明,本文皆为“Traceless”原创,转载请保留文章出处。
Last modification:July 2nd, 2020 at 11:49 am
如果觉得我的文章对你有用,请随意赞赏