LeetCode 2330: Valid Palindrome IV Solution

Master LeetCode problem 2330 (Valid Palindrome IV), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2330. Valid Palindrome IV

Medium

Two Pointers String

Problem Explanation

Explanation

To solve this problem, we can use a recursive approach combined with a two-pointer technique to check if a given string can be converted into a palindrome by removing at most one character. We will recursively check if the current substring is a palindrome and if not, try removing one character from either end. If we encounter more than one mismatch while checking for a palindrome, we return false. If the entire string is a palindrome or can be made into a palindrome by removing at most one character, we return true.

Algorithm:

Define a helper function isPalindrome to check if a given string is a palindrome.
Implement a recursive function isValidPalindrome that takes the input string and two pointers as parameters.
In the isValidPalindrome function:
- Check if the two pointers have crossed each other. If so, return true.
- If the characters at the pointers match, move the pointers towards the center.
- If the characters do not match, try two possibilities:
  - Move the left pointer to the right and recursively check if the substring is a palindrome.
  - Move the right pointer to the left and recursively check if the substring is a palindrome.
If at any point we find more than one mismatch, return false.
Return true if the entire string is a palindrome or can be made into a palindrome by removing at most one character.

Time Complexity:

The time complexity of this approach is O(n), where n is the length of the input string. This is because we are traversing through the string only once.

Space Complexity:

The space complexity is O(n) due to the recursive calls and the call stack.

Solution Code

class Solution {
    public boolean validPalindrome(String s) {
        return isValidPalindrome(s, 0, s.length() - 1, false);
    }
    
    public boolean isValidPalindrome(String s, int left, int right, boolean deleted) {
        if (left >= right) {
            return true;
        }
        
        if (s.charAt(left) == s.charAt(right)) {
            return isValidPalindrome(s, left + 1, right - 1, deleted);
        } else if (!deleted) {
            return isValidPalindrome(s, left + 1, right, true) || isValidPalindrome(s, left, right - 1, true);
        }
        
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2330 (Valid Palindrome IV)?

This page provides optimized solutions for LeetCode problem 2330 (Valid Palindrome IV) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2330 (Valid Palindrome IV)?

The time complexity for LeetCode 2330 (Valid Palindrome IV) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2330 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2330 in Java, C++, or Python.

Back to LeetCode Solutions