Valid Palindrome II - Practice Coding Problems

Valid Palindrome II - Problem

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

A palindrome reads the same forward and backward. For example, "racecar" and "level" are palindromes.

Your task is to determine if removing zero or one character can make the string a palindrome.

Input & Output

Example 1 — Can Make Palindrome

$ Input: s = "aba"

› Output: true

💡 Note: "aba" is already a palindrome, so we return true without deleting any character

Example 2 — Need One Deletion

$ Input: s = "abca"

› Output: true

💡 Note: We can delete 'c' to get "aba" or delete 'b' to get "aca", both are palindromes

Example 3 — Cannot Make Palindrome

$ Input: s = "abc"

› Output: false

💡 Note: No matter which character we delete, we cannot make it a palindrome with just one deletion

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String that might need one character removed

Process

Use two pointers to find mismatches efficiently

Output

Return true if palindrome possible with ≤1 deletion

Key Takeaway

🎯 Key Insight: When two pointers find a mismatch, try skipping either character - if either option creates a palindrome, return true!

Asked in

F Facebook 45 M Microsoft 38 a Amazon 32 G Google 28

The key insight is to use two pointers from both ends. When characters match, move inward. When they mismatch, try skipping either the left or right character and check if the remaining substring is a palindrome. Best approach is two pointers with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Optimized Approach	O(n)	O(1)	Use two pointers from ends, when mismatch try skipping either character
Brute Force - Try All Deletions	O(n²)	O(n)	Try removing each character and check if result is palindrome

Two Pointers - Optimized Approach — Algorithm Steps

Initialize left and right pointers
Compare characters at both pointers
If match, move both pointers inward
If mismatch, try skipping left OR right character
Check if remaining substring is palindrome

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

Place left at start, right at end

Find Mismatch

Move pointers until characters don't match

Try Both Options

Skip left OR right character and check palindrome

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(char* s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

bool solution(char* s) {
    int left = 0, right = strlen(s) - 1;
    
    while (left < right) {
        if (s[left] == s[right]) {
            left++;
            right--;
        } else {
            // Try skipping left character or right character
            return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
        }
    }
    
    return true;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass with two pointers, at most one additional palindrome check

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables and no extra data structures

✓ Linear Space

125.0K Views

High Frequency

~15 min Avg. Time

3.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Optimized Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler