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

题目

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

示例 1:

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答一

设置变量来保存已知最长的子串长度，以及当期的子串长度。
使用数组来保存当期的子字符串。
当遇到重复的字符时，先计算数组当期字符串的长度，看是否比最长的要长，是则更新最长长度。
接着从数组中重复的字符开始截取子串，继续追加字符，直到下一次再遇到重复字符。
需要注意的是：不要漏掉最后一个子串。

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $maxLen = 0;
        $currLen = 0;
        $length = strlen($s);
        $currArr = [];

        for ($i = 0; $i < $length; $i++) {
            $index = array_search($s[$i], $currArr);
            if ($index === false) {
                array_push($currArr, $s[$i]);
            } else {
                $currLen = count($currArr);
                $currLen > $maxLen and $maxLen = $currLen;

                array_splice($currArr, 0, $index+1);
                array_push($currArr, $s[$i]);
            }
        }

        $currLen = count($currArr);
        $currLen > $maxLen and $maxLen = $currLen;

        return $maxLen;
    }
}

执行用时：20 ms, 在所有 PHP 提交中击败了62.69%的用户

内存消耗：19 MB, 在所有 PHP 提交中击败了21.03%的用户

通过测试用例：987 / 987

解答二

更换直接使用子字符串的数据格式来替代数组保存子串。
相比于数组操作，字符串的操作效率更高，所以速度提升明显。

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $maxLen = 0;
        $currLen = 0;
        $length = strlen($s);
        $currStr = '';

        for ($i = 0; $i < $length; $i++) {
            $index = strpos($currStr, $s[$i]);
            if ($index === false) {
                $currStr .= $s[$i];
            } else {
                $currLen = strLen($currStr);
                $currLen > $maxLen and $maxLen = $currLen;

                $currStr = $index+1 == $currLen ? '' : substr($currStr, $index+1);
                $currStr .= $s[$i];
            }
        }

        $currLen = strLen($currStr);
        $currLen > $maxLen and $maxLen = $currLen;

        return $maxLen;
    }
}

执行用时：12 ms, 在所有 PHP 提交中击败了92.31%的用户

内存消耗：19.1 MB, 在所有 PHP 提交中击败了15.64%的用户

通过测试用例：987 / 987

解答三

思考不用新建一个字符串的方式去存储零时子串，而是用一个头索引标记当前子串即可，这样内存使用肯定会下来，速度不好说。

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $maxLen = 0;
        $currLen = 0;
        $currStart = 0;
        $length = strlen($s);

        for ($i = 0; $i < $length; $i++) {
            for ($j = $currStart; $j < $currStart + $currLen; $j++) {
                if ($s[$i] === $s[$j]) {
                    $currLen > $maxLen and $maxLen = $currLen;
                    $currStart = $j + 1;
                    $currLen = $i - $j;
                    continue 2;
                }
            }
            $currLen++;
        }

        return $currLen > $maxLen ? $currLen : $maxLen;
    }
}

执行用时：12 ms, 在所有 PHP 提交中击败了92.31%的用户

内存消耗：18.6 MB, 在所有 PHP 提交中击败了60.77%的用户

通过测试用例：987 / 987

解答四 ✅

尝试使用Array中的hashmap功能是记录是有已存在字符。
并且Array中的映射不清除，这样虽然内存会多占用一点，但是性能会更高。

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $max = $start = 0;
        $total = strlen($s);
        $arr = [];

        for ($i = 0; $i < $total; $i++) {
            if (isset($arr[$s[$i]]) && $arr[$s[$i]] >= $start) {
                $i - $start > $max and $max = $i - $start;
                $start = $arr[$s[$i]] + 1;
            }
            $arr[$s[$i]] = $i;
        }

        return $i - $start > $max ? $i - $start : $max;
    }
}

执行用时：8 ms, 在所有 PHP 提交中击败了98.21%的用户

内存消耗：18.9 MB, 在所有 PHP 提交中击败了23.08%的用户

通过测试用例：987 / 987

对比别人写的C++解答

感觉C++还是要快一些的。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int maxlen = 0;
        vector<int> exist(130,0);
        int i=0;
        for(int j=0; j<n; ++j){
            exist[s[j]]++;
            while(exist[s[j]]>=2) exist[s[i++]]--;
            maxlen=max(maxlen,j-i+1);
        }
        return maxlen;
    }
};

执行用时：8 ms, 在所有 C++ 提交中击败了86.52%的用户

内存消耗：7.7 MB, 在所有 C++ 提交中击败了76.77%的用户

通过测试用例：987 / 987

对比别人java的解答

java感觉好像开挂了，只用了4 ms，但是内存占用多了很多。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (queue.contains(s.charAt(i))){
                maxLength = Math.max(maxLength, queue.size());
                while (queue.poll() != s.charAt(i));
            }
            queue.offer(s.charAt(i));
        }
        return Math.max(maxLength, queue.size());
    }
}

执行用时：4 ms, 在所有 Java 提交中击败了86.45%的用户

内存消耗：41.3 MB, 在所有 Java 提交中击败了64.42%的用户

通过测试用例：987 / 987

本作品采用《CC 协议》，转载必须注明作者和本文链接