🦄 Glass-Hoof Mirror: K-Edit Palindrome

Difficulty: Intermediate Tags: strings, two-pointers, palindrome, greedy Series: CS 101

Problem

Can you turn a string into a palindrome by changing at most k characters?

A palindrome reads the same forwards and backwards (like "racecar", "level", or "noon"). Your job is to determine if a string can become a palindrome with k or fewer character substitutions.

What's a Palindrome?

A palindrome is a string that's identical when reversed: - "racecar" → reverse → "racecar" ✓ - "hello" → reverse → "olleh" ✗

Input

data = {
    's': str,  # The string to check
    'k': int   # Maximum number of character changes allowed
}

Output

bool  # True if can become palindrome with ≤ k changes, False otherwise

Constraints

• 1 ≤ len(s) ≤ 100,000
• 0 ≤ k ≤ len(s) // 2
• String contains only ASCII letters
• Aim for O(n) time - one pass through the string!

Examples

Example 1: One Change Makes it a Palindrome

Input:  {'s': 'racer', 'k': 1}
Output: True

Why?

Original: r a c e r
Mirrored: r e c a r
          ↓ ↓ ✓ ↓ ↓
Compare:  ✓ ✗ ✓ ✗ ✓

Mismatches at positions 1 and 3 (a≠e, e≠a). But these are the same pair mirrored! - Change either s[1] or s[3] → only 1 change needed - 1 ≤ k, so True

Result: "reCer" or "racar" (both palindromes, 1 change)

Example 2: Not Enough Changes

Input:  {'s': 'unicorn', 'k': 2}
Output: False

Why?

Original: u n i c o r n
Mirrored: n r o c i n u
          ↓ ↓ ↓ ✓ ↓ ↓ ↓
Compare:  ✗ ✗ ✗ ✓ ✗ ✗ ✗

Mirrored pairs that don't match: - s[0] vs s[6]: u ≠ n (1 change needed) - s[1] vs s[5]: n ≠ r (1 change needed) - s[2] vs s[4]: i ≠ o (1 change needed)

Total: 3 mismatched pairs → 3 changes needed - 3 > k (which is 2), so False

Example 3: Already a Palindrome

Input:  {'s': 'level', 'k': 0}
Output: True

Why? "level" is already a palindrome. No changes needed. 0 ≤ 0, so True.

Example 4: Not a Palindrome, No Changes Allowed

Input:  {'s': 'levels', 'k': 0}
Output: False

Why?

Original: l e v e l s
Mirrored: s l e v e l
          ↓ ↓ ✓ ✓ ↓ ↓
Compare:  ✗ ✗ ✓ ✓ ✗ ✗

Has mismatches, but k=0 means no changes allowed. False.