The oldest string without repeating characters

Category Difficulty Likes Dislikes
algorithms Medium (30.73%). 2250 –
Tags

hash-table | two-pointers | string | sliding-window

Companies

Example 1:

Input:"abcabcbb"Explanation: Because the oldest string without repeating characters is"abc"So its length is 3.Copy the code

Example 2:

Input:"bbbbb"Explanation: Because the oldest string without repeating characters is"b"So its length is 1.Copy the code

Example 3:

Input:"pwwkew"Explanation: Because the oldest string without repeating characters is"wke"So its length is 3. Please note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

1 window

Here we use two Pointers

A range is represented by two Pointers

The needle keeps moving

The range is changing

We call this process moving Windows

Speaking of no repetition, we would immediately use Set

The scope of our window is

[right,left]

We add all the window elements to the Set

If in the process of moving left, that is, adding new elements

The element is found in Set

We’re going to move right behind that element

This keeps the elements within the window from repeating

/* * @lc app=leetcode.cn id=3 lang=javascript * * [3] The largest string without repeated characters */
/** * @param {string} s * @return {number} */
var lengthOfLongestSubstring = function (s) {
	let [max, left, right] = [0.0.0]
	const set = new Set(a)while (right < s.length) {
		if(! set.has(s[right])) { set.add(s[right++]) max =Math.max(max, right - left)
		} else {
			set.delete(s[left++])
		}
	}
	return max
};
Copy the code

2 window Optimization

Here our left is moving step by step

Until the duplicate element is removed

[left] === s[right] == right

Set.delete (s[left++])

So now the range of elements in set is [left,right]

Set.has (s[right]) does not exist, that is, false

So go if(! set.has(s[right]))

Up here, left is step by step

S [left] === s[right

then

If you have a duplicate

We take the subscript of the repeating element and assign it directly to left

Instead of the left moving step by step

Until s[left] === s[right]

And then I’m going to start with (left,right)

We need to find out what is

  • s[left] === s[right]
  • left

So if we use map

The store is

<index,value>

We’re after [left,right]

When S [right] finds a duplicate in the range

Let’s pretend this is s[right_2].

We just make left equal to right_2 plus 1

So that the range [right_2 + 1,right]

< value, subscript >

var lengthOfLongestSubstring = function (s) {
	let [max, left, right] = [0.0.0]
	let map = new Map(a)while (right < s.length) {
		if (map.has(s[right]))
			left = Math.max(map.get(s[right]) + 1, left)
		map.set(s[right], right++)
		max = Math.max(max, right - left)
	}
	return max
};
Copy the code