Introduction

In this blog post, we will explore how to solve the LeetCode problem "680" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 <= 105 s consists of lowercase English letters.

Explanation

• High-level approach: Use two pointers, left and right, to iterate inwards from the start and end of the string. If s[left] and s[right] are not equal, it means one of them has to be removed to make the string a palindrome. Check if the substring from left + 1 to right (inclusive) or the substring from left to right - 1 (inclusive) is a palindrome.
  • Palindrome check: The palindrome check is done using a similar two-pointer approach.
  • Early exit: If at any point neither removing the left nor the right character results in a palindrome, return False.

• Runtime Complexity: O(n), where n is the length of the input string.
• Storage Complexity: O(1)

Code

    def validPalindrome(s: str) -> bool:
    """
    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 <= 105
    s consists of lowercase English letters.
    """

    def is_palindrome(sub_s: str) -> bool:
        left, right = 0, len(sub_s) - 1
        while left < right:
            if sub_s[left] != sub_s[right]:
                return False
            left += 1
            right -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return is_palindrome(s[left + 1:right + 1]) or is_palindrome(s[left:right])
        left += 1
        right -= 1
    return True