The oldest string without repeating characters

1. Violent solution

Time: O(N^3) Space: O(N)

  1. Set two Pointers, left and right, to the first element
  2. Move the right pointer one by one until the value to which the right pointer points equals the value to which the left pointer points terminates the loop
  3. Resets the right pointer so that the right pointer is equal to the left
  4. Repeat steps 2 and 3 until the left pointer has no value to point to

2. Slide Windows

Time complexity: O(N) Space complexity: O(N)

  1. Set both the left and pointer to the first element and store it in the map array
  2. Move the right pointer one by one until the value to which the right pointer points is equal to the left pointer, storing the current string length, and move the left pointer to the right to the end of the repeating element
  3. And so on, until the traversal is complete, storing the maximum string length
var lengthOfLongestSubstring = function (s) {
    // hash set to record whether each character has ever appeared
    const occ = new Set(a);const n = s.length;
    // The right pointer, starting with -1, means we are to the left of the string's left boundary and have not started moving
    let rk = -1,
        ans = 0;
    for (let i = 0; i < n; ++i) {
        if(i ! =0) {
            // The left pointer moves one space to the right to remove a character
            occ.delete(s.charAt(i - 1));
        }
        while (rk + 1< n && ! occ.has(s.charAt(rk +1))) {
            // Keep moving the right pointer
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        // The i-rk character is an extremely long non-repeating character substring
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
};
Copy the code