680. Valid Palindrome II


Problem Description

The problem requires determining if a given string s can be made into a palindrome by removing at most one character. A palindrome is a word, phrase, number, or other sequences of characters which reads the same forward and backward, ignoring spaces, punctuation, and capitalization. For example, 'radar' is a palindrome, while 'racecars' is not. However, 'racecars' can become a palindrome by removing the 's', which becomes 'racecar' is a palindrome because it reads the same backward as forward. The challenge here is to decide whether such a removal is possible to achieve a palindrome with at most one deletion.

Intuition

To understand the given solution, we should recognize two things:

  1. If a string does not need any character removal to be a palindrome, it means that the characters at the start and end of the string (and so on moving inward) match.
  2. If one mismatch is found, we get a choice - to remove a character from either the left or the right at the point of mismatch and check if the resulting substrings could form a palindrome.

The solution uses a two-pointer approach:

  • Start with two pointers, one at the beginning (i) and one at the end (j) of the string.
  • Move both pointers towards the center, checking if the characters are the same.
  • If a mismatch is discovered, there are two substrings to check: one without the character at i and one without the character at j. We use the helper function check() to verify if either substrings can form a palindrome.
  • If we can successfully verify one substring as a palindrome, we conclude that the original string can be a palindrome after removing at most one character.
  • We continue checking until we either find a proper substring that is a palindrome or exit because we have checked all characters without violating the palindrome property.

The key is the helper function check(i, j) which checks if the substring from i to j is a palindrome by iterating through the substring and comparing characters at the start and end, moving inwards.

By carefully applying the check() function only when a mismatch is found, the given algorithm efficiently decides whether one can obtain a palindrome with at most one deletion.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

The solution's core relies on a two-pointer approach while also incorporating a helper method to reduce redundancy. Here's the process step-by-step:

  1. Initial Two-pointer Setup: Initialize two pointers, i and j, representing the start and the end of the string s. These two pointers will progressively move towards the center.

  2. First Pass - Checking Palindrome: Move both pointers towards the center, implied by i < j. If the characters at i and j match (s[i] == s[j]), we can safely continue. This loop continues until a mismatch is found (when s[i] != s[j]) or until the entire string is checked.

  3. Handling Mismatches - Utilizing the Helper Function: Upon encountering a mismatch, the solution must determine whether omitting one of the characters can lead to a palindrome. This is where the helper method, check(i, j), comes into play. When s[i] != s[j], two checks are made:

    • One check leaves out the character at the end (check(i, j - 1)), assuming this might be the extra character causing a non-palindrome.
    • The other check omits the character at the start (check(i + 1, j)), assuming this might be the non-matching odd one out.
  4. The Helper Method - check(i, j): The method takes two indices and checks if the substring between them (s[i] to s[j]) is a palindrome. It uses the same two-pointer technique, now applying it within the narrower range. It returns True if a palindrome is detected, False if not.

  5. Single Character Removal Decision: After calling the check() method for both possible single removals, we use logical OR (or) to combine the results. If either case returns True, the original string can be converted to a palindrome by removing one character. The function then returns True.

  6. Completing the Loop: If no mismatch is found, the loop ends, and we can assume the string is already a palindrome or can be made into one with a single removal (might be a character at the start or the end which doesn't interfere with the palindrome property).

  7. Final Return: If we reach outside the loop without returning False, the string must be a palindrome, and the function returns True.

This approach provides an optimal solution as it only scans the string once and performs the minimum necessary comparisons, obeying the constraints set by the problem (at most one character removal).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the string s = "abca" to illustrate the solution approach. We need to determine if it's possible to make s into a palindrome by removing at most one character.

  1. Initial Two-pointer Setup: We start with two pointers, i = 0 (pointing to 'a') and j = 3 (pointing to 'a'). The string looks like this: abca, with i at the first character and j at the last.

  2. First Pass - Checking Palindrome: We compare s[i] and s[j]. Since s[0] is 'a' and s[3] is also 'a', there's a match, so we move both i and j towards each other (now i = 1, j = 2).

  3. Finding a Mismatch: Now i = 1 is pointing to 'b' and j = 2 is pointing to 'c'. They don't match (s[i] != s[j]). We need to check if removing one character makes it a palindrome. We call the check() function twice as follows:

    • check(1, 1): This omits the character at j (the 'c') and checks if ab is a palindrome.
    • check(2, 2): This omits the character at i (the 'b') and checks if ca is a palindrome.
  4. The Helper Method - check(i, j): When we run check(1, 1), it instantly returns True as it's effectively checking a single character 'b', which is trivially a palindrome. We don't need to perform check(2, 2) as we've already found a potential palindrome by removing 'c'.

  5. Single Character Removal Decision: Because check(1, 1) returned True, we have confirmed that by removing one character ('c'), the string s could be turned into a palindrome. Therefore, for the input abca, the function would return True.

  6. Completing the Loop: In this example, the mismatch was found, and the check() function indicated a palindrome is possible, so the loop is completed successfully.

  7. Final Return: Since we found that a single removal can lead to a palindrome, the function would return True for the string s = "abca".

This walkthrough demonstrates how we can efficiently determine that the string "abca" can become a palindrome by removing at most one character, 'c' in this case, leading to the palindrome "aba".

Solution Implementation

1class Solution:
2    def validPalindrome(self, string: str) -> bool:
3        # Helper function to check if substring string[left:right+1] is a palindrome
4        def is_palindrome(left, right):
5            while left < right:
6                if string[left] != string[right]:
7                    return False
8                left, right = left + 1, right - 1
9            return True
10
11        left, right = 0, len(string) - 1  # Initialize pointers at both ends of the string
12
13        # Iterate while the two pointers don't cross each other
14        while left < right:
15            # If the characters at the current pointers don't match
16            if string[left] != string[right]:
17                # Check for palindrome by removing one character - either from the left or right
18                # If either case returns true, the function returns true
19                return is_palindrome(left, right - 1) or is_palindrome(left + 1, right)
20            # Move both pointers towards the center
21            left, right = left + 1, right - 1
22
23        # If the string is a palindrome or can be made into one by removing a single character
24        return True
25
1class Solution {
2
3    // This method checks if a string can be a palindrome after at most one deletion.
4    public boolean validPalindrome(String s) {
5        // Iterate from both ends towards the center
6        for (int left = 0, right = s.length() - 1; left < right; ++left, --right) {
7            // If two characters are not equal, try to skip a character either from left or right
8            if (s.charAt(left) != s.charAt(right)) {
9                // Check if the substring skipping one character on the left is a palindrome
10                // or
11                // Check if the substring skipping one character on the right is a palindrome
12                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
13            }
14        }
15        // If no mismatched characters found, it's already a palindrome
16        return true;
17    }
18
19    // Helper method to check whether a substring defined by its indices is a palindrome
20    private boolean isPalindrome(String s, int startIndex, int endIndex) {
21        // Iterate over the substring
22        for (int i = startIndex, j = endIndex; i < j; ++i, --j) {
23            // If any pair of characters is not equal, it's not a palindrome
24            if (s.charAt(i) != s.charAt(j)) {
25                return false;
26            }
27        }
28        // No mismatches found, it's a palindrome
29        return true;
30    }
31}
32
1class Solution {
2public:
3    // Function to check whether a given string can be a palindrome by removing at most one character
4    bool validPalindrome(string s) {
5        int left = 0, right = s.size() - 1;
6
7        // Iterate from both ends towards the center
8        while (left < right) {
9            // If mismatch is found, check for the remaining substrings
10            if (s[left] != s[right]) {
11                // Check if the substrings skipping one character each are palindromes
12                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
13            }
14            ++left;
15            --right;
16        }
17
18        // The string is a palindrome if no mismatches are found
19        return true;
20    }
21
22private:
23    // Helper function to check if a substring is a palindrome
24    bool isPalindrome(const string& s, int left, int right) {
25        // Check for equality from both ends towards the center
26        while (left < right) {
27            if (s[left] != s[right]) {
28                return false; // Return false if a mismatch is found
29            }
30            ++left;
31            --right;
32        }
33
34        return true; // Return true if no mismatches are found
35    }
36};
37
1// Function to determine if the string can become a palindrome by removing at most one character
2function validPalindrome(s: string): boolean {
3    // Traverse the string from both ends towards the center
4    for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
5        // If a mismatch is found, try to remove one character at either end
6        if (s.charAt(i) !== s.charAt(j)) {
7            // Check if removing from the start or the end makes a palindrome
8            return isPalindrome(s.slice(i, j)) || isPalindrome(s.slice(i + 1, j + 1));
9        }
10    }
11    // If no mismatches are found or the string is a palindrome, return true
12    return true;
13}
14
15// Helper function to determine if a given string is a palindrome
16function isPalindrome(s: string): boolean {
17    // Traverse the string from both ends towards the center
18    for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
19        // If a mismatch is found, the string is not a palindrome
20        if (s.charAt(i) !== s.charAt(j)) {
21            return false;
22        }
23    }
24    // If no mismatches are found, the string is a palindrome
25    return true;
26}
27

Time and Space Complexity

The given Python code defines a method validPalindrome to determine if a given string can be considered a palindrome by removing at most one character.

Time Complexity:

The time complexity of the main function is generally O(n), where n is the length of the input string s. This is because the function includes a while loop that iterates over each character of the string at most twice - once in the main while loop and once in the check function, which is called at most twice if a non-matching pair is found.

To break it down:

  • The main while loop iterates over the string s, comparing characters from i to j. Each loop iteration takes O(1) time.
  • If a mismatch is found, there are two calls to the helper function check, each with a worst-case time complexity of O(n/2), which simplifies to O(n).

In the worst case, you compare up to n - 1 characters twice (once for each call of check), so the upper bound is 2 * (n - 1) operations, which still results in a linear time complexity: O(n).

Space Complexity:

The space complexity of the code is O(1). No additional space is proportional to the input size is being used, aside from a constant number of integer variables to keep track of indices. The check function is called with different indices but does not use any extra space apart from the input string s, which is passed by reference and not copied.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement priority queue?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄