Valid Palindrome Ii Solution for Wipro

Company: Wipro · Difficulty: Easy · Topics: String, Two Pointers, Greedy

Problem Statement

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

A palindrome is a string that reads the same forward and backward.

Examples

Example 1:

Input: s = "aba"

Output: true

Explanation: The string is already a palindrome, so no deletion is needed.

Example 2:

Input: s = "abca"

Output: true

Explanation: We can delete the character 'c' to get "aba" which is a palindrome.

Example 3:

Input: s = "abc"

Output: false

Explanation: No single character deletion can make it a palindrome.

Intuition

We can use two pointers to check if the string is a palindrome. When we find a mismatch, we can try deleting either the left or right character and check if the remaining string is a palindrome.

Approach

Approach 1: Two Pointers with Recursion (Optimal)

1. Use two pointers (left and right) to check palindrome

2. When characters don't match, try deleting left or right character

3. Check if remaining string is palindrome

4. Return true if either deletion works

Approach 2: Helper Function

1. Create a helper function to check if substring is palindrome

2. When mismatch found, check two possibilities:

Delete left character: check s[left+1, right]
Delete right character: check s[left, right-1]

3. Return true if either works

Approach 3: Brute Force

1. Try deleting each character one by one

2. Check if resulting string is palindrome

3. Return true if any deletion works

Dry Run

Let's trace through Example 2: s = "abca"

Two Pointers Approach:

left = 0, right = 3
s[0] = 'a', s[3] = 'a' → match, move pointers
left = 1, right = 2
s[1] = 'b', s[2] = 'c' → mismatch
Try deleting 'b': check "aca" → not palindrome
Try deleting 'c': check "aba" → palindrome
Return true

Key Insights

1. Two Pointers: Efficient way to check palindrome

2. Single Deletion: Only need to try one deletion when mismatch found

3. Greedy Choice: Try both possibilities when mismatch occurs

4. Early Return: Return true as soon as one deletion works

Edge Cases

1. Already palindrome: "aba" → true

2. Single character: "a" → true

3. Two characters: "ab" → true (delete either)

4. No solution: "abc" → false

5. Even length: "abba" → true

Time and Space Complexity

Time Complexity: O(n) - Single pass through string
Space Complexity: O(1) - Only constant extra space used