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 <= 105s consists of lowercase English letters.In #680 Valid Palindrome II, the goal is to determine whether a string can become a palindrome after deleting at most one character. A palindrome reads the same forward and backward, which naturally suggests a two-pointer technique.
Start with two pointers: one at the beginning and one at the end of the string. Move them inward while characters match. If a mismatch occurs, you are allowed to remove one character. At this point, check whether skipping either the left character or the right character forms a valid palindrome. This greedy decision works because only one deletion is permitted.
To verify the remaining substring, you can run a simple palindrome check between the updated indices. This keeps the implementation clean and efficient.
The overall time complexity remains O(n) since each character is visited at most a constant number of times, while the space complexity is O(1) because the algorithm uses only a few pointers.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers with One Allowed Deletion | O(n) | O(1) |
| Brute Force (try deleting each character) | O(n^2) | O(1) |
NeetCode
This approach uses the two-pointer technique to check if the string is a palindrome after removing at most one character. Start with two pointers at the beginning and end of the string. Move inward while the characters at these pointers are equal. If a mismatch occurs, there are two possibilities: either remove the character at the left pointer or the right pointer. If either results in a palindrome, then the string can be considered a valid palindrome after one deletion.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) as we use a constant amount of extra space.
1#include <stdbool.h>
2#include <string.h>
3
4bool isPalindromeRange(char * s, int i, int j) {
5
The solution uses helper function isPalindromeRange to check if a sub-range of the string is a palindrome. The main function, validPalindrome, attempts to verify if the string becomes a palindrome after removing one mismatched character, if any.
This approach uses recursion to accomplish the same task. When encountering the first differing pair of characters, we make two recursive calls: one ignoring the left character and one ignoring the right character. If either recursive call results in a valid palindrome, the whole string can be considered a valid palindrome after a single character deletion.
Time Complexity: O(n)
Space Complexity: O(1) by avoiding deep recursive stacks through tail optimization.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of palindrome checking problems are commonly asked in FAANG and other top tech company interviews. They test understanding of two-pointer strategies and edge-case handling.
The optimal approach uses the two-pointer technique. Traverse from both ends of the string and allow one mismatch where you skip either the left or right character and verify the remaining substring. This keeps the time complexity linear.
No complex data structure is required. The problem can be solved efficiently using simple string indexing and two pointers, making it both memory-efficient and easy to implement.
The two-pointer approach works because palindromes are symmetric around their center. By comparing characters from both ends simultaneously, you can quickly detect mismatches and handle constraints like allowing one deletion.
The C solution applies a helper function that manages recursive calls whenever a mismatched pair of characters is found, implementing an efficient recursive resolution.