Here is the leetcode link for this problem
I recently tried two medium-difficulty Leetcode problems with [Jaseem Abid](https://www.linkedin.com/in/jaseemabid/, my partner in leet crime.
Although distinct, these two problems were very similar in some ways, so although I will publish them as separate write-ups, I think that I was able to apply lessons learned in the first to the second:
Here’s my writeup for that next one: 19) Longest Palindromic Substring.
I started with a classic mistake: I spent a little two long trying to come up with solutions. These three approaches commented out at the top represent 6 minutes.
I realized that iterating through every possible substring and checking to see if it had repeating characters would have n cubed time complexity, so I sort of balked and tried to think of a better way, but didn’t quite succeed, so I ended up just trying that n cubed approach.
// iterate through each index
// save longst found substring as I iterate a second time from index
// n^3
// dynamic programming
// substrings
// iterate from each index,
// bfs
// split it half from middle index
// from there check substrings backwards and forwards
//
function lengthOfLongestSubstring(s: string): number {
let longestSubString: string[] = [s[0]]
let sA = s.split[''] // < Turn it into an array
for (const startingIndex in sA){
const remainingString = sA.slice(startingIndex, sA.length)
const tempString: string[] = []
for (const j in remainingString){
if (tempString.includes(remainingString[j])){
break
} else {
tempString.push(remainingString[j])
}
}
if (tempString.length > longestSubString.length){
longestSubString = tempString
}
console.log(tempString)
}
return longestSubString.length
};I invite you to disagree, but I think the result of my session was some really difficult to read code. Also, it doesn’t work - it also outputs ‘1’. The console.log(tempString) line never gets called.
Considering I took 2 weeks off from leetcode and hopped onto one of my first medium problems, I don’t think I did awful. However, I certainly failed this in the interview context.
Jaseem had some awesome feedback, some of it quite new to me. He told me about something called “Wishful Programming”. Wishful programming is a technique somewhere between writing real code and pseudocode where you substitute solvable problems for placeholder functions, or other structures, that may or may not exist.
When I heard this I likened it to art - one of the keys to being a good painter is starting big, and moving into the details. If you paint the general shapes and colors first before the details, you can avoid creating details that you need to do over. Also in art, it can be easy to get perspective, color and contour pretty wrong if you are too focused on the “small picture”.
I think that wishful thinking shows how this is the same for programming. It’s better to get the shape of the algorithm down before picking less important details. In the above code, I got caught up in the method by which slicing up substrings, even though the substrings themselves were really just abstractions I relied on to get their length. And yet much of my code was focused on string manipulation, making it much harder to read and to reason about.
I tried again, although to be honest I still didn’t really use wishful programming. Having tried a version of the sliding window technique, I was able to try it more earnestly:
function lengthOfLongestSubstring(s: string): number {
if (!s.length) return 0
// sliding window
let start = 0
let end = 1 // exclusive
let longestSubstring = 1
const ss = s.split('')
let workingChars = new Set()
workingChars.add(ss[0])
let longest = 1
// abcabcbb length of 8
// so we start with a window of 0, 1
// And a set of just 'a'
while (start < s.length){
if (workingChars.has(ss[end])){
workingChars = new Set()
}
if (workingChars.has(ss[end])){
workingChars = new Set()
start++
if (end < start) end = start
continue
}
longest = Math.max(longest, end-start)
console.log({start, end, workingChars, longest})
workingChars.add(ss[end])
end++
if (end > s.length) break
}
return longest
};This approach uses a set, which seemed like a good approach. However it always seems to return the length of the entire string. I’m actually coming back to this after a couple days so I won’t even try to consider what I was trying to do here, I’ll just move onto a successful solurion.
I found this solution, which is very close to what I was aiming for:
function lengthOfLongestSubstring(s: string): number {
let start=0, end=0, max=0;
let mySet = new Set();
while(end < s.length) {
if(!mySet.has(s[end])) {
mySet.add(s[end++]);
max = Math.max(max, mySet.size);
} else mySet.delete(s[start++]);
}
return max;
}Clever thing #1
Wow wild! I just learned that end++ evaluates to the current value of end AND THEN increments afterwards. Would have though it evaluates to the incremented value.
Clever thing #2 Also really interesting how they are using the set size. This is really clever - it allows the set data structure to have two jobs
- The obvious one of checking if we are still in non-repeat territory
- An easy way to check the length of our window.
Clever thing #3
Using!mySet.has(...) is more readable than starting with the mySet.has(...) case.
I think it is just as doable to do something like end-start, but not sure yet.
I’m just gonna go ahead and type this out in english because it’s fun.
I think it is just as doable to do something like end-start, but not sure yet.
I’m just gonna go ahead and type this out in english because it’s fun.
We have a string of length n. Start out with a collapsed window at the beginning of the string. As long as the end of the window is less than the length (same as saying less than or equal to max index), go on one of two paths.
First, check if the that window contains duplicates. If not, update the current length if it’s longer than the previous length. Also increment the end for next go.
If it DOES contain duplicates, all we need to do is delete the duplicate value from the set and increment the start. That’s really the most confusing part to me. Incrementing the start, that makes sense. Move the window forward - keeping moving it forward until the dupe is gone. Although we should only have to move it forward once, as we are doing this AS SOON AS A DUPLICATE appears, so any duplicates that come up will always be at the beginning and end of the window.
As such, we move the window start forward.
But…why remove the current value from the set?
Well, the next thing that will be run is that if(!mySet.has(s[end])) line. If we didn’t remove the value from the set, we’d get stuck here, because we wouldn’t make it past this conditional and we’d go back to the duplicate case again, just moving the starting window farther and farther forward. In fact, the while loop would never finish, because end would stop progessing.
I have to tell myself ‘don’t worry!’ here. If we remove the duplicate value from the set, we now do make it past the if(!mySet.has(s[end]) conditional, and the first thing we do in that conditional block as add or value. And then of course increment end! So next time through, we’ll catch a duplicate value - we won’t miss it.
In this way, the values added to the set are always the first instance of that value found.
I feel this is probably entirely clear by now or I am just getting more and more confusing, but maybe the easiest way to illustrate why/how this works is to take an example string, abcabcdefg
Right when we start out, end is 0 so we check to see if a is in our set. It’s not, so we add it and increment end to point to an index of 1.
Cool, now it’s 1, so we move on. Everything is chill until end is 4. At this point, we check that first conditional and find, oh shit! a IS already in our set! Don’t panic everyone.
BECAUSE a is already in our set, we’re going to halt forward incrementation of end. Instead, we’ll remove a from the set and we’ll move our start value to be 1, omitting that first a. Few. Okay now our window doesn’t include any dupes.
We go back and check that first conditional of if (!mySet.has(s[end])) and find that this time, our set has NO a value, which is the value of our current end of 4. Dope. That means we can go ahead and add it, increment the end, and continue on our way. Once we get to the final index, we can exit our for loop, and whatever that longest window length was, that’s what our function returns.
Okay. I won’t use the expression “beating a dead horse” because that implies it’s productive to beat live horses, but I certainly spelled that out pretty clearly.
Let me see if I can write it without aide now.
YES. I got it! Should look almost the same:
function lengthOfLongestSubstring(s: string): number {
let start = 0, end = 0, max = 0;
const uniqueNums = new Set()
const finalIndex = s.length - 1
while (end <= finalIndex){
if (!uniqueNums.has(s[end])){
uniqueNums.add(s[end++])
max = Math.max(max, uniqueNums.size)
} else uniqueNums.delete(s[start++])
}
return max
};Man that really felt like cheating. But I learned a lot more from studying someone else’s answer than my own uncoordinated code. The way I rationalize this - all too soon, I will forget this algo and get a chance to try it as if for the first time, with just an inkling of this method.
Return #1
Peeked at the approach - couldn’t remember a ton of the details. Came up with this after 2 simple errors and 4:27 secons:
function lengthOfLongestSubstring(s: string): number {
let longSub = 0
// okay so the idea is create a window.
// The window starts super small
let start=0, end=0, max = 0
// So I'm gonna make a set
// And check to see if I have seen a char from set, if so,
// move start forward
const uniqueChars = new Set()
while (end < s.length){
if (!uniqueChars.has(s[end])){
uniqueChars.add(s[end++])
longSub = Math.max(longSub, end-start)
} else {
uniqueChars.delete(s[start++])
}
}
return longSub
};Okay tried again, fixed it up again, was able to write it from memory in 59 seconds:
function lengthOfLongestSubstring(s: string): number {
let start = 0, end = 0, max = 0
let q = new Set()
while (end < s.length){
if (!q.has(s[end])){
q.add(s[end++])
max = Math.max(max, end-start)
} else q.delete(s[start++])
}
return max
};Return #2
I found the order of lines 7 and 8 matter:
function lengthOfLongestSubstring(s: string): number {
let start = 0, end = 0, max = 0
const uniqueChars: Set<string> = new Set()
while (end < s.length){
if (!uniqueChars.has(s[end])){
uniqueChars.add(s[end++])
max = Math.max(end-start, max)
} else uniqueChars.delete(s[start++])
}
return max
};The incrementing line here actually does two functions - it increments end so we can continue, and it also adds one to end for this current permutation.
Correct:
uniqueChars.add(s[end++])
max = Math.max(end-start, max)Incorrect:
max = Math.max(end-start, max)
uniqueChars.add(s[end++])Take the following example:
a--b--c--d--a--b--c
0--1--2--3--4--5--6
abcd is the longest string. As I iterate through my algo, the farthest I’ll get before adjusting my start value is 3.
3-0 is of course ‘3’, but the longest string I’ve found here is abcd, with a length of 4. So by placing the incrementing before the length evaluation line, I can correctly evaluate the length of a the 0-indexed string. Super eloquent! Because I grabbed this answer from someone else, I didn’t realize I was doing this.
Another thing I didn’t totally realize was that JS and TS allowed strings to be accessed by index without be converted into an array.
Tried again
And made a silly omission it took me a while to find - I did Math.max(right, max)
instead of Math.max(right-left, max), as just discussed.