# Valid Palindrome II

• Click here to see the full article post

• Can you please explain why you think the second approach is Greedy? My understanding about Greedy is that you must figure out a correct way to decide which character to remove, rather than trying both ways and check out which way works.

For example, Problem 665, Non-decreasing array, is similar to this one. In Problem 665, there is a greedy approach to decide how to modify an element in the array to make the array non-decreasing. But in this problem, I don't see we have a counterpart.

• @kamfung2017 We are faced with the decision of what `S[k]` to remove to check whether the result is a palindrome. When say, `S[0] = S[len(S) - 1]`, then it could still be the case that removing `S[0]` or `S[len(S) - 1]` results in a palindrome too, but these choices are weakly dominated by solving on `(S[1], ..., S[len(S) - 2])`.

This is what I meant by a "greedy" choice: between local options we chose the one that dominates the other. At the end when we only have to check at most 2 such `k`, I consider this a stopping condition. By all means if you prefer to call it something else, do so. I was just trying to choose a relatively descriptive word for the heading.

• I see. I took it for granted that we should skip all the front-back pairs of equal character, and thought the story only began at the first unequal pair. Now I can see your solution does have the Greedy component in it. Thanks.

• This post is deleted!

• The solution for the second approach is really poorly worded. This link explains the methodology better:
http://www.geeksforgeeks.org/remove-character-string-make-palindrome/

• I don't understand the indexes. What does (j - k + i) do?

• @david301 When checking `is_pali_range(i, j)`, we wanted to know if all `s[i] == s[j]`, `s[i+1] == s[j-1]`, etc. are true. More generally, this is `s[i+d] == s[j-d]`.

So, as `k` ranges from `i` to `j`, put `k = i+d`. Then `j-d = j + i - k`. So we want `s[k] == s[j+i-k]`.

• ``````class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
l, r = 0, len(s)-1
while l < r:
if s[l] == s[r]:
l += 1
r -= 1
else:
tmp1 = s[:l]+s[l+1:]
tmp2 = s[:r]+s[r+1:]
return tmp1 == tmp1[::-1] or tmp2 == tmp2[::-1]:
return True
``````

• May I ask if the question requires adding one character to anywhere in a string, how to check whether the original string can be changed to a palindrome?

• Easy to understand solution :)

class Solution {
public:
bool validPalindrome(string s) {

``````    int len = s.length();
int back = len-1;

string temp1 = s, temp2 = s;
bool flag = false;

for(int front=0;front<len/2;front++){
if(s[front] != s[back-front]){
temp1.erase(front,1);
temp2.erase(back-front,1);
flag = true;
break;
}
}
if(flag == true){
string chk1 = temp1, chk2 = temp2;
reverse(chk1.begin(),chk1.end());
reverse(chk2.begin(),chk2.end());

if(temp1==chk1 or temp2==chk2)
return true;
else
return false;
}
return true;
}
``````

};

• This is my really easy and well-commented solution without a helper function.

• Second Approach :Here is my solution using while loop instead of for loop which makes it easy to deal with index calculation,

public bool ValidPalindrome(string s) {
int start=0; int end = s.Length - 1;
while(start< end)
{
if(s[start] != s[end])
return IsPalindrome(s,start+ 1, end) ||IsPalindrome(s,start, end -1) ;
start++;
end--;
}
return true;
}

``````public bool IsPalindrome(string s, int start, int end)
{
while(start< end)
{
if(s[start] != s[end])
return false;
start++;
end--;
}
return true;
}``````

• Is it my mistake or is the solution incorrect?
For example, try this test case:

``````    System.out.println(s.isPalindrome(new String("pidbliassaqozokmtgahluruufwbjdtayuhbxwoicviygilgzduudzgligyviciowxbhuyatdjbwfuurulhagtmkozoqassailbdip").replace("v", "")));
System.out.println(s.validPalindrome("pidbliassaqozokmtgahluruufwbjdtayuhbxwoicviygilgzduudzgligyviciowxbhuyatdjbwfuurulhagtmkozoqassailbdip"));
``````

The output is true for the first line yet false for the second.

Am I not understanding the problem? What's going on here?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.