算法研究-无重复字串

这个系列是笔者练习LeetCode上的算法题的记录&分享

题目

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

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

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

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

题解

根据示例可以得出一些需要注意的地方
1. 得到的是字串，并不是子序列
2. 得到的是一个无重复字符的字串

第一次尝试的思路是，遍历所有字符，每次，检查首字符和首字符最后一次出现的地方，然后重复这个过程。代码如下

public int LengthOfLongestSubstring(string s)
{
    string getMaxLength = "";
    for (int i = 0; i < s.Length; i++)
    {
        Debug.Log("TAG " + i);
        string getStr = GetChars(s,i);

        if (getStr.Length > getMaxLength.Length)
        {
            getMaxLength = getStr;
        }

        if (getMaxLength.Length >= (s.Length - i))
        {
            break;
        }
    }
    Debug.Log("TAG MaxStr is " + getMaxLength);
    return getMaxLength.Length;
}

string GetChars(string str,int i)
{
    string get = str;
    Debug.Log("TAG str is " + str + " and i " + i);
    if (str.Length > 1) {
        if (str.LastIndexOf(str[i]) != -1 && str.LastIndexOf(str[i]) != i)
        {
            get = GetChars(str.Substring(i, str.LastIndexOf(str[i])), 0);
        }
        else
        {
            get = str.Substring(i);
        }
    }
    return get;
}

但是无法判断其他字符是否有重复出现，以及代码中没有对 “bbbbb” 此类做处理

---

看了题解之后，得到以下思路（滑动窗口）：

将字符串依次放入一个集合，每次，放入之后最大长度 +1 ，如果放入的字符已经有了，则判断，剔除已有字符之前所有字符后，新字符串是否比最大长度更长（此处应该是 大于等于），如果更长，则剔除并更新长度，如果没有则停止判断。

代码如下：

public int LengthOfLongestSubstring(string s)
{
    int maxLength = 0;
    List<char> getChar = new List<char>();
    for (int i = 0; i < s.Length; i++)
    {
        if (getChar.Contains(s[i]))
        {
            getChar.RemoveRange(0, getChar.IndexOf(s[i])+1);
            getChar.Add(s[i]);
        }
        else {
            getChar.Add(s[i]);
        }
        if (getChar.Count > maxLength) {
            maxLength = getChar.Count;
        }
    }
    return maxLength;
}