For this problem we are going to utilize the sliding window technique. Using this technique, we will have two pointers, and if the substring has no duplicates, we can increase the window by 1.
To determine if we don't have any duplicates we will use Set.
As we are traversing the string, we need to add the current letter to our set, and if we try to add it again, it won't work (this is how Sets work, they only have unique characters/elements).
function findLongestSubString(s) {
let newSet = new Set()
let pointerOne = 0
let pointerTwo = 0
let longSub = 0
}
All we've done in the above is create a new set (sets don't allow duplicates) and we've created two pointers that we will use to traverse the string. We've also created a longSub variable set to 0 since we are going to need to update this as we compare substrings.
function findLongestSubString(s) {
let newSet = new Set()
let pointerOne = 0
let pointerTwo = 0
let longSub = 0
while (pointerOne < s.length) {
}
}
In the next step above, we've said while the pointer is less then the length of the string traverse the string. Then we will say that if the set doesn't have the character that pointerOne is on, then we want to add it to the set.
function findLongestSubString(s) {
let newSet = new Set()
let pointerOne = 0
let pointerTwo = 0
let longSub = 0
while (pointerOne < s.length) {
if (!newSet.has(s.charAt(pointerOne))) {
newSet.add(s.charAt[pointerOne])
}
}
}
Again, looking at what we have above, if the set doesn't have the character at the position of pointerOne, then add it to the set.
We will then use Math.max, which compares two elements, to see which has the longest length and we will then set that to the maxLength.
function findLongestSubString(s) {
let newSet = new Set()
let pointerOne = 0
let pointerTwo = 0
let longSub = 0
while (pointerOne < s.length) {
if (!newSet.has(s.charAt(pointerOne))) {
newSet.add(s.charAt[pointerOne])
longSub = Math.max(longSub, newSet.size)
}
}
}
Now, what we need to do is move pointerOne forward, we can do so by just saying pointerOne++.
function findLongestSubString(s) {
let newSet = new Set()
let pointerOne = 0
let pointerTwo = 0
let longSub = 0
while (pointerOne < s.length) {
if (!newSet.has(s.charAt(pointerOne))) {
newSet.add(s.charAt[pointerOne])
longSub = Math.max(longSub, newSet.size)
pointerOne++
}
}
}
Now this will take us through the letters in the string, but at some point we will hit a duplicate. In this case, we want to remove the current letter that pointerTwo is on (the first character in the substring).
function findLongestSubString(s) {
let newSet = new Set()
let pointerOne = 0
let pointerTwo = 0
let longSub = 0
while (pointerOne < s.length) {
if (!newSet.has(s.charAt(pointerOne))) {
newSet.add(s.charAt[pointerOne])
longSub = Math.max(longSub, newSet.size)
pointerOne++
}
else {
newSet.delete(s.charAt[pointerTwo])
pointerTwo++
}
}
return longSub
}
Eventually we we will get to a blank space (the end of the sting), and that means we've gone through everything. So, we can just return the longSub which is going to be a number.
Top comments (0)