We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Palindrome IV

Number: 2468

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given a 0-indexed string s consisting only of lowercase English letters, determine whether it is possible to make s a palindrome by performing exactly one or exactly two operations. In each operation, you can change any character to any other character. Return true if it is possible; otherwise, return false.

Key Insights

  • Use the two pointers technique to compare characters symmetrically.
  • Count the number of mismatched character pairs.
  • If there are 0 mismatches, the string is already a palindrome. For strings with length 1, one operation still preserves the palindrome, while for lengths ≥2, you can always perform 2 operations by changing a symmetric pair.
  • If there is exactly 1 mismatch, one operation is sufficient.
  • If there are exactly 2 mismatches, two operations can fix both pairs.
  • More than 2 mismatches cannot be corrected with only 1 or 2 operations.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string (we scan roughly half of the string).
Space Complexity: O(1), using only a few auxiliary variables.

Solution

We use a two-pointer approach, one starting from the beginning and the other from the end, to count mismatched pairs.

  • If no mismatch is found, the string is already a palindrome. For a single character, one operation keeps it a palindrome; for strings with length ≥2, you can use two operations to change a symmetric pair to a new identical pair.
  • If exactly one pair is mismatched, a single operation on one of those characters can correct the difference.
  • If exactly two mismatches are found, you can correct each by performing an operation on each mismatched pair.
  • If more than two mismatched pairs exist, it is impossible to form a palindrome with exactly one or two operations.

The solution thus involves iterating from start until the midpoint, counting mismatches, and then checking if the count is 0, 1, or 2 to return true. Otherwise, return false.

Code Solutions

# Function to determine if s can be made a palindrome with exactly 1 or 2 operations.
def validPalindromeIV(s):
    n = len(s)
    mismatches = 0
    # Loop over only half of the string.
    for i in range(n // 2):
        # Compare the character from the beginning and its corresponding character from the end.
        if s[i] != s[n - 1 - i]:
            mismatches += 1
            # If more than 2 mismatches, return False immediately.
            if mismatches > 2:
                return False
    # If the number of mismatches is 0, 1, or 2, we can achieve a palindrome with exactly 1 or 2 operations.
    return True

# Example tests.
print(validPalindromeIV("abcdba"))  # Expected output: True
print(validPalindromeIV("aa"))      # Expected output: True
print(validPalindromeIV("abcdef"))  # Expected output: False
← Back to All Questions