# Two solutions (optimized and recursive) Java and C#

• Java:

Optimized (Accepted):

``````public boolean validPalindrome(String s)
{
int left = 0, right = s.length() - 1;

while (left < right)
{
if (s.charAt(left) == s.charAt(right))
{
left++; right--;
}
else
{
//remove right
int templeft = left, tempright = right - 1;

while (templeft < tempright)
{
if (s.charAt(templeft) != s.charAt(tempright)) break;
templeft++; tempright--;

if (templeft >= tempright) return true;
}

//remove left
left++;

while (left < right)
{
if (s.charAt(left) != s.charAt(right)) return false;
left++; right--;
}
}
}
return true;
}
``````

Brute Force (Recursive) (Time Limit Exceeded):

``````public boolean validPalindrome(String s)
{
return validPalindrome(s, 0, s.length() - 1, false);
}
private boolean validPalindrome(String s, int left, int right, Boolean mismatch)
{
if (right - left <= 1) return true;

if (s.charAt(left) != s.charAt(right))
{
if (mismatch == true)
return false;

return validPalindrome(s, left, right - 1, true) || validPalindrome(s, left + 1, right, true);
}
else
{
return validPalindrome(s, left + 1, right - 1, mismatch);
}
}
``````

C#:

Optimized (Accepted):

``````public bool ValidPalindrome(string s)
{
int left = 0, right = s.Length - 1;

while (left < right)
{
if (s[left] == s[right])
{
left++; right--;
}
else
{
//remove right
int templeft = left, tempright = right - 1;

while (templeft < tempright)
{
if (s[templeft] != s[tempright]) break;
templeft++; tempright--;

if (templeft >= tempright) return true;
}

//remove left
left++;

while (left < right)
{
if (s[left] != s[right]) return false;
left++; right--;
}
}
}
return true;
}
``````

Brute Force (Recursive) (Time Limit Exceeded):

``````public bool ValidPalindrome(string s) //brute force
{
return ValidPalindrome(s, 0, s.Length - 1, false);
}
private bool ValidPalindrome(string s, int left, int right, bool mismatch)
{
if (right - left <= 1) return true;

if (s[left] != s[right])
{
if (mismatch == true)
return false;

return ValidPalindrome(s, left, right - 1, true) || ValidPalindrome(s, left + 1, right, true);
}
else
{
return ValidPalindrome(s, left + 1, right - 1, mismatch);
}
}
``````

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