Here is the leetcode URL for this string
Wishful programming was mentioned in 18) Longest Substring Without Repeating Characters, but I didn’t really use it until this one. Here is my first attempt at wishful programming:
function longestPalindrome(s: string): string {
// validPalindrome = s[0]
middleIndex = middle
width = 0
subString = getIt()
while (middleIndex < s.length - 1){
}
if (isPalindrome(subString)){
// and both sides are in bounds
validPalindrome = Math.max(subString.length, validPalindrome.length)
width++
} else {
width = 0
}
if palindrome, palindrome = s.slice(start, end)
if NOT a palindrome, move end farther along
};
// It’s sort of like half pseudo-code, reminiscent of spanglish is half english. I like the getIt() function, which was code I was confident I could figure out later, so I just pretended like it did its job and moved on.
Jaseem and I uncovered a very powerful benefit to this - if I ended up pivoting directions, I would only lose the 1 or 2 seconds it took me to write getIt() versus if I had written that function out from the get go.
Possibly even more importantly, I wouldn’t be as averse to pivoting, since I haven’t invested as much time into an initial approach. This shouldn’t really be a factor because it falls into the sunk-costs fallacy, but emotions can be charged during an interview, which can lead to falling into traps like this.
Jaseem had a fancy, complicated technique he showed me in which he created a double nested array in which the first index represented the start of the window and the second index represented the end. He set every value to 0 initially to show that they hadn’t been checked, then on a diagonal set each string representing an individual letter to true to show it was, by nature of being a single character, palindromic.
There was a fancy attempt at dynamic programming here, but it was an old answer of his, and although we were impressed by it, we couldn’t really see a reason why this was necessary for this problem.
I’m fresh off writing 18) Longest Substring Without Repeating Characters though, so I’m actually going to try to just apply that sliding window technique directly to this as well since it seems so similar.
Here is a sort of goofily similar approach:
function longestPalindrome(s: string): string {
// babad
// return longe=est valid palindrome
// .slice is inclusive/exclusive
// OR just 0/exclusive if only one char passed
if (s.length < 1) return ''
if (s.length === 1) return s[0]
let start = 0, end = 1, longestPal = ''
let isPalindrome = (inputString: string) => {
console.log(inputString)
if (inputString.length % 2 === 0){
let middleRight = inputString.length / 2
return inputString.slice(middleRight) === inputString.slice(middleRight, inputString.length)
} else {
let middle = Math.floor(inputString.length / 2)
return inputString.slice(middle) === inputString.slice(middle+1, inputString.length)
}
}
let longestString = (stringOne: string, stringTwo: string) => {
if (stringOne.length >= stringTwo.length) return stringOne
return stringTwo
}
while (end < s.length){
let window = s.slice(start, end)
if (isPalindrome(window)){
longestPal = longestString(longestPal, s.slice(start, end++))
} else {
start++
}
}
return longestPal
};But that’s silly. We gotta use width, not a true start/end window.
HA. That last sample was with 3 minutes to go. I changed it to this before I hit the 20m mark:
function longestPalindrome(s: string): string {
// babad
// return longe=est valid palindrome
// .slice is inclusive/exclusive
// OR just 0/exclusive if only one char passed
if (s.length < 1) return ''
if (s.length === 1) return s[0]
let middle = 0, radius = 0, longestPal = ''
let isPalindrome = (inputString: string) => {
console.log(inputString)
if (inputString.length % 2 === 0){
let middleRight = inputString.length / 2
return inputString.slice(middleRight) === inputString.slice(middleRight, inputString.length)
} else {
let middle = Math.floor(inputString.length / 2)
return inputString.slice(middle) === inputString.slice(middle+1, inputString.length)
}
}
let longestString = (stringOne: string, stringTwo: string) => {
if (stringOne.length >= stringTwo.length) return stringOne
return stringTwo
}
while (middle + radius < s.length){
if (middle - radius < 0) continue
let window = s.slice(middle - radius, middle + radius + 1)
longestPal = longestString(longestPal, window)
}
return longestPal
};But of course this timed out, it’s not done - the while loop goes on forever. Actually took 6 minutes of changes to really get this idea ironed out:
function longestPalindrome(s: string): string {
// babad
// return longe=est valid palindrome
// .slice is inclusive/exclusive
// OR just 0/exclusive if only one char passed
if (s.length < 1) return ''
if (s.length === 1) return s[0]
let middle = 0, radius = 0, longestPal = ''
let isPalindrome = (inputString: string) => {
console.log(inputString)
if (inputString.length % 2 === 0){
let middleRight = inputString.length / 2
return inputString.slice(middleRight) === inputString.slice(middleRight, inputString.length)
} else {
let middle = Math.floor(inputString.length / 2)
return inputString.slice(middle) === inputString.slice(middle+1, inputString.length)
}
}
let longestString = (stringOne: string, stringTwo: string) => {
if (stringOne.length >= stringTwo.length) return stringOne
return stringTwo
}
while (middle + radius < s.length){
if (middle - radius < 0){
middle++
continue
}
let window = s.slice(middle - radius, middle + radius + 1)
if (s[middle - radius] === s[middle + radius]){
longestPal = longestString(longestPal, window)
}
radius++
}
return longestPal
};Unfortunately…this doesn’t really handle the detection of even palindromes. So. I think it’s time to look at some answers.
This is what perplexity ‘came up with’:
function longestPalindrome(s: string): string {
if (s.length < 2) return s;
let start = 0, maxLength = 1;
function expandAroundCenter(left: number, right: number) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
const currentLength = right - left + 1;
if (currentLength > maxLength) {
start = left;
maxLength = currentLength;
}
left--;
right++;
}
}
for (let i = 0; i < s.length; i++) {
expandAroundCenter(i, i); // Odd length palindromes
expandAroundCenter(i, i + 1); // Even length palindromes
}
return s.slice(start, start + maxLength);
}It looks pretty neat, and it performs pretty well.
Okay let me think this through line by line.
If there are 0 or 1 characters in the string, return the string. We only have two variables to change - start and Maxlength.
We define a function expandAroundCenter that we can presume can be reused for odd and even cases.
This function takes a left and a right. When we use it later on, it looks like the odd incantation passes both of these values as the same. The even incantation passes i, and then i + 1.
In this function, we check a few things to stay in the while loop:
- left has to be more than or equal to 0.
- the
rightneeds to be less than the length of the string - familiar to 18) Longest Substring Without Repeating Characters - This last one is cool! Right has to be equal to left, or we quit the while loop
Then in the while loop, we get to a sort of index-fiddly thing where we are keeping track of NOT ONLY the maxLength palindrome we’ve found, but also the start, which is the just the place we store the left value that corresponds to the longest palindrome we’ve found.
Phew. Okay. So this all makes sense, and isn’t crazy complicated, it’s just a lot. Let’s see if I can reproduce it from scratch. Let’s go.
Okay 4 minutes in ran it, got a compile error:
function longestPalindrome(s: string): string {
if (s.length < 2) return s // handle cases where string is just one or no letters
let start = 0, maxLength = 0
const expandOutFromCenter(left: number, right: number) => {
while (left >= 0 && right < s.length && left == right){
let window = s.slice(left, right+1)
if (window.length > maxLength){
start = left
maxLength = window.length
}
left--
right++
}
}
for (const i = 0; i < s.length; s++){
expandOutFromCenter(i, i)
expandOutFromCenter(i, i+1)
}
return s.slice(start, start + maxLength)
// increment through every starting position of string for even and odd cases
};Okay fixed a few bugs and added in console logs:
function longestPalindrome(s: string): string {
if (s.length < 2) return s // handle cases where string is just one or no letters
let start = 0, maxLength = 0
const expandOutFromCenter = (left: number, right: number) => {
console.log({left, right})
while (left >= 0 && right < s.length && left === right){
let window = s.slice(left, right+1)
if (window.length > maxLength){
start = left
maxLength = window.length
}
left--
right++
}
}
for (let i = 0; i < s.length; i++){
expandOutFromCenter(i, i)
expandOutFromCenter(i, i+1)
console.log('-----')
}
return s.slice(start, start + maxLength)
// increment through every starting position of string for even and odd cases
};HA. I got it!
8.26 minutes
My problem was that in my while loop conditional I was comparing the indexes of left and right, not their values - this was sort of clear from the console logs I got:
{ left: 0, right: 0 }
{ left: 0, right: 1 }
-----
{ left: 1, right: 1 }
{ left: 1, right: 2 }
-----
{ left: 2, right: 2 }
{ left: 2, right: 3 }
-----
{ left: 3, right: 3 }
{ left: 3, right: 4 }
-----
{ left: 4, right: 4 }
{ left: 4, right: 5 }
-----I looked at these and saw hmm. We’re not progressing through the for loop. Here’s the reproduced winner:
function longestPalindrome(s: string): string {
if (s.length < 2) return s // handle cases where string is just one or no letters
let start = 0, maxLength = 0
const expandOutFromCenter = (left: number, right: number) => {
console.log({left, right})
while (left >= 0 && right < s.length && s[left] === s[right]){
if (right - left + 1 > maxLength){
start = left
maxLength = window.length
}
left--
right++
}
}
for (let i = 0; i < s.length; i++){
expandOutFromCenter(i, i)
expandOutFromCenter(i, i+1)
console.log('-----')
}
return s.slice(start, start + maxLength)
// increment through every starting position of string for even and odd cases
};Weirdly the performance is WAY worse than the Perplexity code.
Perplexity’s solution: 83ms Mine one: 661ms.
What gives? I bet you can spot it.
After looking back over my code I got it - it’s this line: let window = s.slice(left, right+1)
I am creating a new string every while loop. But I don’t need a whole string. I just need to know the length of the window.
OKAY NOPE
That’s sort of correct - that seems to account for 40ms of latency. But the other 538 just come from the two console logs!
function longestPalindrome(s: string): string {
if (s.length < 2) return s // handle cases where string is just one or no letters
let start = 0, maxLength = 0
const expandOutFromCenter = (left: number, right: number) => {
while (left >= 0 && right < s.length && s[left] === s[right]){
let window = right + 1 - left
if (window > maxLength){
start = left
maxLength = window
}
left--
right++
}
}
for (let i = 0; i < s.length; i++){
expandOutFromCenter(i, i)
expandOutFromCenter(i, i+1)
}
return s.slice(start, start + maxLength)
// increment through every starting position of string for even and odd cases
};^ Here’s my final solution, which is now 81ms. Sweet! That was a tough 40 minutes or so of studying but I feel good. I will try to reproduce these both tomorrow and see how I do.
Return 1
Okay it’s been a day! I got it in 14:56 after a couple challenges:
function longestPalindrome(s: string): string {
if (s.length < 2) return s
// okay so I need to do this with the expand from center function
// The expand from center function starts with a left and a right
// and then it continues expanding as long as each expansion left === right
// one quirk of it is that it has to save the "start" of palindrome as well as, at least, some way to calculate the end as well, so we can actually return what we've found
let start = 0
let length = 0
const expandFromCenter = (left: number, right: number) => {
while (s[left] === s[right] && left > -1 && right < s.length){
if (right-left > length){
start=left
length=right-left
}
left--
right++
}
}
for (let i = 0; i < s.length; i++){
expandFromCenter(i, i+1)
expandFromCenter(i, i)
}
return s.slice(start, start+length+1)
};Problems I faces:
- I left in a
console.logat one point, which caused leetcode to error out in a way I hadn’t seen - the stdout limit was exceeded! It was written asoutput exceeded, but when I removed theconsole.logthe submission worked splendidly, executing within a competitive time complexity. - I accidentally incremented
rightandleftat first - I had to add the
+1on the last line, but I’m not totally sure why. I just did it intuitively in response to the strings that were being returned to me.
Let me think about though. Ah right! .slice’s second argument is exclusive.
Return 2
time: 5:35
Features I forgot:
Originally I thought that I could just do Math.max(maxLength, end-start), but forgot I also have to save the start. I wonder if there’s any way around saving two separate variables.