DSCPPAS276 - Editorial

editorial
, ,
1

Problem Statement:

You are given a string S. The task is to determine if the string can be transformed into a palindrome by deleting at most one character.

Approach:

To determine if the string can be a palindrome after deleting at most one character, we can use a two-pointer technique. The key idea is to check the string from both ends towards the center and identify the first mismatch. When a mismatch is found, there are two possible ways to potentially fix the string:

  1. Skip the character at the left pointer.
  2. Skip the character at the right pointer.

If either of these modifications results in a valid palindrome, the original string can be considered a valid palindrome after deleting one character.

Step-by-Step Explanation:

  1. Two-Pointer Technique:

    • Use two pointers, left starting at the beginning of the string and right starting at the end.
    • Move the left pointer forward and the right pointer backward towards the center, comparing the characters at each position.

  2. Handling Mismatch:

    • If the characters at left and right are the same, move both pointers closer to the center.
    • If the characters are different, check two scenarios:
      1. Skip the character at left and check if the remaining substring (from left + 1 to right) is a palindrome.
      2. Skip the character at right and check if the remaining substring (from left to right - 1) is a palindrome.

  3. Checking Substring for Palindrome:

    • Use a helper function isPalindrome to check if a given substring (bounded by left and right indices) is a palindrome.

  4. Return Result:

    • If either scenario (skipping left or right) results in a palindrome, return true.
    • If no mismatches are found during the initial comparison (i.e., the string is already a palindrome), return true.

  5. Edge Case:

    • A single character string or an empty string is trivially a palindrome.

Complexity:

  • Time Complexity: The time complexity is O(N), where N is the length of the string. This is because each character is checked at most twice.

  • Space Complexity: The space complexity is O(1) since no additional space is required beyond a few variables.