Valid Palindrome II

LeetCode 680 | Difficulty: Easy

Easy

Problem Description

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 <= 10^5`

- `s` consists of lowercase English letters.

Topics: Two Pointers, String, Greedy

---

Approach

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 133 ms)

Metric	Value
Runtime	133 ms
Memory	41.5 MB
Date	2022-04-02

Solution

public class Solution {
    public bool ValidPalindrome(string s) {
        return ValidPalindrome(s,0, s.Length-1, false);

}

public bool ValidPalindrome(string s, int low, int high, bool isDeleted)
{
    if(low>high) return false;
    while(low<high)
    {
        if(s[low]!=s[high])
        {
            if(isDeleted) return false;
            else return ValidPalindrome(s, low+1, high, true) ||  ValidPalindrome(s, low, high-1, true); 
        }
        else { low++; high--;}
        
    }
    return true;
}
}

📜 1 more C# submission(s)

Submission (2018-09-25) — 192 ms, N/A

public class Solution {
    public bool ValidPalindrome(string s) {
        return ValidPalindrome(s,0, s.Length-1, false);

}

public bool ValidPalindrome(string s, int low, int high, bool isDeleted)
{
    if(low>high) return false;
    while(low<high)
    {
        if(s[low]!=s[high])
        {
            if(isDeleted) return false;
            else return ValidPalindrome(s, low+1, high, true) ||  ValidPalindrome(s, low, high-1, true); 
        }
        else { low++; high--;}
        
    }
    return true;
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.