Valid Palindrome II - Leetcode 680 - Python

[@chagsssss]

Great flow of explanation. I try to solve a problem and regardless of whether I can or not, I watch the video of the problem on your channel. Either way, it helps build up the fundamentals for me.

[@gianniprocida3332]

Yes definitely

[@CJ-ff1xq]

Reversing a string is not really the optimal way to determine if it’s a palindrome. It uses extra memory and you also have to iterate over the whole string. With two pointers you only iterate half the string. Still O(n) but should be a bit faster on average! But I see you mentioned it at the end of the video anyway so great job.

[@numberonep5404]

a solution with pointers, trivial but still class Solution: def validPalindrome(self, s: str) -> bool: def isPal(lf, rh): while lf

[@harigovind11]

One of Facebook's favourite interview question. Was asked this twice by Facebook itself.

[@swarupsarangi734]

# USING THE HELPER FUNCTION class Solution: def helper(self,s,p1,p2) : while p1 < p2 : if s[p1] != s[p2]: return False p1 += 1 p2 -= 1 return True def validPalindrome(self, s: str) -> bool: l, r = 0, len(s) - 1 while l < r: if s[l] != s[r]: # check if elements l + 1 till r + 1 is pallindrome # check if element l till r is pallindrome return ( self.helper(s,l + 1, r) or self.helper(s,l, r - 1) ) l += 1 r -= 1 return True

[@Ankit-hs9nb]

with helper function O(1) space class Solution: def validPalindrome(self, s: str) -> bool: left = 0 right = len(s) - 1 while left < right: if s[left] != s[right]: return self.is_palindrome(s, left+1, right) or self.is_palindrome(s, left, right-1) left += 1 right -= 1 return True def is_palindrome(self,s, start_index, end_index): while (start_index < end_index): if s[start_index] != s[end_index]: return False start_index += 1 end_index -= 1 return True

[@nilanjandey9604]

ohk. Now i understood. i have to skip and check that whether the remaining string is palidrome or not. got it. Thanks

[@aghilannathan8169]

Absolutely no fucking way. I was doing Valid Palindrome and for whatever reason, I just could not solve it. I open KZbin to see if NeetCode has a video on it and you posted it 30 minutes ago, just my luck.

[@riyaz3409]

class Solution: def validPalindrome(self, s: str) -> bool: def checkValid(l,r): while l

[@dice4572]

I tried doing this by skipping the element that's not equal (if s[l+1] == s[r]: l+=1 and vice versa) and i almost understand why that doesn't work but not quite. can someone pls explain why this strat doesn't work?

[@aryehakierman6388]

I also couldnt understand why it didnt work untill I found this use case: "ececabbacec"

[@flatmapper]

Thanks NeetCode. I love my solution without allocating extra memory fun validPalindrome(string: String): Boolean { var i = 0 var j = string.lastIndex while (i < j && string[i] == string[j]) { i++ j-- } return isPalindrome(string, i + 1, j) || isPalindrome(string, i, j - 1) } fun isPalindrome(string: String, start: Int, end: Int): Boolean { var i = start var j = end while (i < j) { if (string[i] != string[j]) { return false } i++ j-- } return true }

[@jbaltariu]

I still don't get it. Why isn't it O(n^2) if you're reversing the string each time you check for a palindrome? Isn't that operation linear as well?

[@aryehakierman6388]

good question,the reason its not O(N^2) is because we arnt reversing the string for every character in the string,we are at most reversing them once or twice, therefor it is O(N+2N) => O(N)

[@geekydanish5990]

class Solution: def validPalindrome(self, s: str) -> bool: def is_valid_palindrome(l,r): while l < r: if s[l] != s[r]: return False l +=1 r -=1 return True l_pointer = 0 r_pointer = len(s)-1 while l_pointer < r_pointer: if s[l_pointer] == s[r_pointer]: l_pointer +=1 r_pointer -=1 else: if is_valid_palindrome(l_pointer+1,r_pointer): return True if is_valid_palindrome(l_pointer,r_pointer-1): return True return False return True

[@barissimsek]

It's not clear from the question but this solution won't work if there are two differences in the string as it returns on the first occurrence. The questions says at most one change but it doesn't say there is only one diff max.

[@harishkumarbikki1060]

In skipL, keeping r+1 as higher limit and will it cause index out of bound error?

[@rajatagrawal7016]

Java class Solution { public boolean validPalindrome(String s) { char ar[]= s.toCharArray(); int j=ar.length-1; int i=0; for(;i

[@inessben8679]

Hello neetcode, Thank you so much for your amazing and clear videos. I have a request, Can you please explain a problem called " Minimum steps to reduce to 1 " ?

[@tanayraj2991]

Is it possible to do this using LCS? If the LCS of the string and its reverse version is less than str.length-1 then it is not valid palindrome.

[@apiyush]

Shouldn't the time complexity be O(n^2) since we are iterating over n//2 times and using string reversal (i.e. s == s[::-1]) ? (n//2) * (n) ~= O(n^2) ?

[@quickscope754]

You would only need to use the string reversal at most twice though because once you have an s[l] that does not match and s[r], you return either true or false and do not continue checking the rest of the string. Therefore its just O(n).

[@madhumalar789]

Can I get guidelines to practice on ABAP in the site you mentioned ?

[@datboi20]

I'm a little confused about how this solution is not runtime of O(n^2). The outside while loop is 0(n). Then the reversal (skipL/skipR[::-1]) inside of the while loop is O(n). Since it's nested, I'd think that would be O(n^2). Am I missing something?

[@rjesh2062]

No you are travelling each character at most one time which is n steps which means it should be O(length) at worst case

[@randomlyasked]

Any chance of posting leetcode contest solutions? 3rd and 4th if possible 🥺

[@vdyb745]

Awesome !!!! I admire your commitment !!! Thank you so much ....

[@thanirmalainagappan9472]

Thank you very much

[@tranminhquang4541]

Why th is this one labeled "easy"?

[@ammarhindi9253]

Can you create a hash map and check if the number of Keys in the map is greater than 2 return false since there is more than two unique characters that if we choose to delete any of them it would still not be a palindrom. Return true if the amount of Keys is 2 or less?

[@rjesh2062]

For anyone having the same doubt it would not work coz you cannot change the positions of the characters and count of characters will not give you a Idea about whether a string is a palindrome or Not..Eg: acdacc , aadccc

[@rajatagrawal7016]

Keep going I wait for your videos.

[@AntoineJacques]

def validPalindrome(self, s: str) -> bool: l=0 r=len(s)-1 while l < r: if s[l] == s[r]: l+=1 r-=1 else: return s[l:r] == s[l:r][::-1] or s[l+1:r+1] == s[l+1:r+1][::-1] return True

[@_Ahmed_15]

Should be a medium

[@__________________________6910]

Again I'm first NeetCode

[@coder4937]

Congrats🎉

[@NeetCode]

lol nice streak

[@masternobody1896]

@@NeetCode reverse link list

[@sproutboot]

2:00

[@alanhuang7831]

Heyy