Valid Palindrome II - Leetcode 680 - Python

0:00 - Read the problem
0:25 - Drawing Explanation
4:01 - Coding Explanation

leetcode 680

#meta #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[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.

[CJ-ffxq]

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.

[harigovind]

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

[swarupsarangi]

# 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

[poptart-br]

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

def isPal(lf, rh):
while lf<rh:
if s[lf]==s[rh]:
lf+=1
rh-=1
else:
return False
return True

n = len(s)-1
l, r = 0, len(s)-1
while l<r:
if s[l]==s[r]:
l+=1
r-=1
else:
return isPal(l, r-1) or isPal(l+1, r)
return True

[aghilannathan]

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

[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
}

[nilanjandey]

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

[rajatagrawal]

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

for(;i<j;i++, j--){

if(ar[i]!=ar[j]){
// System.out.println(s.substring(i+1, j+1));
// System.out.println(s.substring(i, j));

if(validP(ar, i+1, j)){
return true;
}
if(validP(ar, i, j-1)){
return true;
}

return false;
}


}

return true;
}
public boolean validP(char ar[], int start, int end){
while(start<end){
if(ar[start]!=ar[end]) return false;
start+=1;
end-=1;
}
return true;
}
}

[Ankit-hsnb]

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

[riyaz]

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

[geekydanish]

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

[vdyb]

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

[rohithgorthy]

I am sorry, I have a question if you are reversing the string isnt the time complexity to multiplied by o(n) each time.

[inessben]

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 " ?

[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?

[harishkumarbikki]

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

[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.

[madhumalar]

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

[randomlyasked]

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