Valid Palindrome II easy

Problem Statement

Given a string s, return true if it is a palindrome, or if it can be made a palindrome by removing at most one character.

Example 1

Input: s = "aba" Output: true Explanation: "aba" is already a palindrome.

Example 2

Input: s = "abca" Output: true Explanation: You could remove the character 'c' to make "aba" which is a palindrome.

Steps

1. Check if the string is already a palindrome: If it is, return true.
2. Iterate through the string: Compare characters from the beginning and end, moving inwards.
3. Handle discrepancies: If characters don't match, we have two options:
   • Remove the character at the beginning and check if the remaining substring is a palindrome.
   • Remove the character at the end and check if the remaining substring is a palindrome.
   • If either of these results in a palindrome, return true.
4. Return false: If no solution is found after checking all discrepancies, return false.

Explanation

The solution efficiently checks if a string is a palindrome or can be made one by removing at most one character. The core logic lies in handling mismatches between characters at the beginning and end of the string. By recursively checking the substring after removing either the beginning or end character, we explore all possible single-character removals to determine if a palindrome can be formed.

The use of helper function IsPalindrome avoids repetitive code and improves readability. The string.Substring method is used for efficiently creating substrings without unnecessary copying.

Code

using System;

public class Solution {
    public bool ValidPalindrome(string s) {
        if (IsPalindrome(s)) return true;

        for (int i = 0; i < s.Length; i++) {
            string s1 = s.Substring(0, i) + s.Substring(i + 1);
            if (IsPalindrome(s1)) return true;
        }

        return false;
    }

    private bool IsPalindrome(string s) {
        int left = 0;
        int right = s.Length - 1;
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}

Complexity

• Time Complexity: O(N), where N is the length of the string. In the worst case, we might iterate through the string once to check if it's a palindrome, and then iterate through it again to check at most N - 1 substrings after removing one character. The IsPalindrome helper function takes O(N/2) which simplifies to O(N).
• Space Complexity: O(N) in the worst case due to the substring creation in the ValidPalindrome function. However, the space used is proportional to the length of the string, and not exponentially increasing. This can be slightly optimized using two pointers without substring creation, resulting in O(1) space complexity (see optimized solution below).

Optimized Code (O(1) Space Complexity)

using System;

public class Solution {
    public bool ValidPalindrome(string s) {
        int left = 0;
        int right = s.Length - 1;

        while (left < right) {
            if (s[left] != s[right]) {
                return IsPalindrome(s, left + 1, right) || IsPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }

    private bool IsPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}

This optimized version avoids the creation of substrings, improving space complexity to O(1). It directly uses pointers within the original string.