680. Valid Palindrome II LeetCode Solution

In this guide, you will get 680. Valid Palindrome II LeetCode Solution with the best time and space complexity. The solution to Valid Palindrome II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Valid Palindrome II solution in C++
Valid Palindrome II solution in Java
Valid Palindrome II solution in Python
Additional Resources

680. Valid Palindrome II LeetCode Solution image

Problem Statement of Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = “aba”
Output: true

Example 2:

Input: s = “abca”
Output: true
Explanation: You could delete the character ‘c’.

Example 3:

Input: s = “abc”
Output: false

Constraints:

1 <= s.length <= 105
s consists of lowercase English letters.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

680. Valid Palindrome II LeetCode Solution in C++

class Solution {
 public:
  bool validPalindrome(string s) {
    for (int l = 0, r = s.length() - 1; l < r; ++l, --r)
      if (s[l] != s[r])
        return validPalindrome(s, l + 1, r) ||  //
               validPalindrome(s, l, r - 1);
    return true;
  }

 private:
  bool validPalindrome(const string& s, int l, int r) {
    while (l < r)
      if (s[l++] != s[r--])
        return false;
    return true;
  }
};
/* code provided by PROGIEZ */

680. Valid Palindrome II LeetCode Solution in Java

class Solution {
  public boolean validPalindrome(String s) {
    for (int l = 0, r = s.length() - 1; l < r; ++l, --r)
      if (s.charAt(l) != s.charAt(r))
        return validPalindrome(s, l + 1, r) || validPalindrome(s, l, r - 1);
    return true;
  }

  private boolean validPalindrome(final String s, int l, int r) {
    while (l < r)
      if (s.charAt(l++) != s.charAt(r--))
        return false;
    return true;
  }
}
// code provided by PROGIEZ

680. Valid Palindrome II LeetCode Solution in Python

class Solution:
  def validPalindrome(self, s: str) -> bool:
    def validPalindrome(l: int, r: int) -> bool:
      return all(s[i] == s[r - i + l] for i in range(l, (l + r) // 2 + 1))

    n = len(s)

    for i in range(n // 2):
      if s[i] != s[~i]:
        return validPalindrome(i + 1, n - 1 - i) or validPalindrome(i, n - 2 - i)

    return True
 # code by PROGIEZ