The oldest string without repeating characters
1. Violent solution
Time: O(N^3) Space: O(N)
- Set two Pointers, left and right, to the first element
- 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
- Resets the right pointer so that the right pointer is equal to the left
- 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)
- Set both the left and pointer to the first element and store it in the map array
- 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
- 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