I. Title Description:

Find the longest substring from the string that does not contain repeated characters, and calculate the length of the oldest string.

Example 1:

Input: “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

Example 2:

Input: “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wke”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.

Second, train of thought analysis

So the first thing that comes to mind is dynamic sliders

  1. I’m going to store the strings between I and j, in a queue,$maxDiffStrTo facilitate next inspection

  1. Keep looking back until you find a value that exists in $maxDiffStr

  2. The queue $maxDiffStr is ejected in turn until the ejected value is equal to the value of the current loop

  3. MaxLen is now recalculated

Third, code writing

class Solution {

    / * * *@param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $len = strlen($s);
        if ($len < 1) {
            return 0;
        }

        $maxLen = 1;
        $maxDiffStr = [$s[0]].for ($i=1; $i < $len; $i{+ +)if (in_array($s[$i].$maxDiffStr)) {  
                while (array_shift($maxDiffStr)! = =$s[$i]) {}}$maxDiffStr[] = $s[$i];
            $maxLen = $maxLen > count($maxDiffStr)?$maxLen : count($maxDiffStr);
        }
        return $maxLen; }}Copy the code

See big guy’s problem solution, as expected better method is still far away

Double pointer + hash table

class Solution {

    / * * *@param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $dic = [];
        $res = 0;
        $i = -1;
        $len = strlen($s);
        for ($j=0; $j < $len; $j{+ +)if (isset($dic[$s[$j]]) {$i = max($dic[$s[$j]], $i);
            }
            $dic[$s[$j]] = $j;
            $res = max($res.$j-$i);
        }
        return $res; }}Copy the code

The first day, xiao CAI CAI on the way…