LeetCode 2330 - Valid Palindrome IV

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

The problem gives us a string s containing only lowercase English letters. We are allowed to perform operations where we change any single character into any other lowercase character. The goal is to determine whether the string can become a palindrome after performing either exactly one operation or exactly two operations.

A palindrome is a string that reads the same forward and backward. This means that for every position i, the character at s[i] must match the character at the mirrored position s[n - 1 - i].

The important detail is that the problem requires exactly one or two operations, not zero operations. Even if the string is already a palindrome, we still must perform at least one operation. Fortunately, we can always modify characters in ways that preserve the palindrome property. For example, in a palindrome like "aa", we can change both characters to "bb" using two operations.

The input size can be as large as 10^5, which means we need an efficient linear-time solution. Any approach that tries many character substitutions explicitly would become too slow.

The key observation is that every mismatched mirrored pair requires at least one operation to fix. If there are too many mismatches, then two operations are not enough.

Several edge cases are important:

Strings of length 1 are already palindromes, and one operation can keep them palindromic.
Strings that are already palindromes must still allow exactly one or two operations.
Strings with many mismatched pairs cannot be repaired within two operations.
Odd-length strings have a middle character that does not need matching.

Approaches

Brute Force Approach

A brute-force solution would try every possible way to change one or two characters and then check whether the resulting string is a palindrome.

For one operation, we could:

Pick every index.
Replace it with every possible lowercase letter.
Check whether the resulting string is a palindrome.

For two operations, we would:

Pick every pair of indices.
Try every pair of replacement characters.
Check whether the result is a palindrome.

This approach is correct because it explicitly explores all valid possibilities. However, it is far too slow.

If the string length is n, then:

One-operation possibilities are roughly 26 * n
Two-operation possibilities are roughly (26 * n)^2

This becomes completely infeasible for n = 10^5.

Optimal Approach

The better solution comes from analyzing what prevents a string from being a palindrome.

A palindrome only cares about mirrored character pairs. For every pair:

If the characters already match, no operation is needed.
If they differ, at least one operation is required to fix that pair.

This means the number of mismatched mirrored pairs directly tells us the minimum number of operations needed.

For example:

"abca" has one mismatch pair: b vs c
"abcdef" has three mismatch pairs

Since we are allowed at most two operations:

If mismatches <= 2, the answer is true
Otherwise, the answer is false

An already-palindromic string also works because:

One operation can modify the center character in odd-length palindromes
Two symmetric operations can preserve even-length palindromes

So the entire problem reduces to counting mismatched mirrored pairs.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26² × n³) or worse	O(n)	Tries all character replacement combinations
Optimal	O(n)	O(1)	Counts mismatched mirrored pairs

Algorithm Walkthrough

Initialize two pointers, one at the beginning of the string and one at the end.
Initialize a counter called mismatches to 0. This counter tracks how many mirrored pairs differ.
While the left pointer is smaller than the right pointer:
Compare the characters at both pointers.
If the characters are different, increment mismatches.
Move the left pointer forward.
Move the right pointer backward.
After scanning all mirrored pairs:
If mismatches is greater than 2, return False.
Otherwise, return True.

The reason this works is that each mismatched pair can always be fixed with exactly one operation by changing either character to match the other.

Why it works

Each mismatched mirrored pair independently requires one operation to repair. No single operation can fix more than one mismatched pair because each operation only changes one character. Therefore, the minimum number of operations required equals the number of mismatched pairs.

If the mismatch count is at most 2, we can always perform one or two operations to create a palindrome. If it exceeds 2, then at least three operations are necessary, so the answer must be false.

Python Solution

class Solution:
    def makePalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        mismatches = 0

        while left < right:
            if s[left] != s[right]:
                mismatches += 1

            left += 1
            right -= 1

        return mismatches <= 2

The implementation follows the two-pointer strategy directly.

The variables left and right track mirrored positions in the string. During each iteration, the algorithm compares the corresponding characters.

Whenever the characters differ, the mismatches counter increases. Each mismatch represents one mirrored pair that requires an operation to fix.

After processing all mirrored pairs, the algorithm checks whether the mismatch count exceeds two. If it does, repairing the string within the allowed operation limit is impossible.

The implementation uses constant extra memory because it only stores a few integer variables.

Go Solution

func makePalindrome(s string) bool {
    left := 0
    right := len(s) - 1
    mismatches := 0

    for left < right {
        if s[left] != s[right] {
            mismatches++
        }

        left++
        right--
    }

    return mismatches <= 2
}

The Go implementation is nearly identical to the Python version.

Go strings are byte slices internally, and since the problem guarantees lowercase English letters only, direct byte indexing is safe and efficient.

No extra arrays or slices are needed. The solution operates entirely with integer indices and a mismatch counter.

Worked Examples

Example 1

Input:

s = "abcdba"

Initial state:

Left Index	Right Index	Characters	Match?	Mismatches
0	5	a vs a	Yes	0
1	4	b vs b	Yes	0
2	3	c vs d	No	1

Final mismatch count is 1.

Since 1 <= 2, return true.

One valid operation:

Change c to d
Result becomes "abddba"

Example 2

Input:

s = "aa"

Initial state:

Left Index	Right Index	Characters	Match?	Mismatches
0	1	a vs a	Yes	0

Final mismatch count is 0.

Since 0 <= 2, return true.

Possible operations:

Change first a to b
Change second a to b

Result becomes "bb".

Example 3

Input:

s = "abcdef"

Initial state:

Left Index	Right Index	Characters	Match?	Mismatches
0	5	a vs f	No	1
1	4	b vs e	No	2
2	3	c vs d	No	3

Final mismatch count is 3.

Since 3 > 2, return false.

At least three operations are required.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character pair is examined once
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan across the string using two pointers. Each iteration processes one mirrored pair, so the runtime grows proportionally with the string length.

The memory usage remains constant regardless of input size because no additional data structures are allocated.

Test Cases

solution = Solution()

assert solution.makePalindrome("abcdba") == True   # One mismatch
assert solution.makePalindrome("aa") == True       # Already palindrome
assert solution.makePalindrome("abcdef") == False  # Three mismatches

assert solution.makePalindrome("a") == True        # Single character
assert solution.makePalindrome("ab") == True       # One mismatch
assert solution.makePalindrome("abc") == True      # One mismatch pair
assert solution.makePalindrome("abba") == True     # Already palindrome
assert solution.makePalindrome("abcba") == True    # Odd-length palindrome

assert solution.makePalindrome("abca") == True     # One mismatch pair
assert solution.makePalindrome("abccaa") == True   # Two mismatch pairs
assert solution.makePalindrome("abcd") == True     # Two mismatch pairs

assert solution.makePalindrome("abcde") == False   # More than two mismatches
assert solution.makePalindrome("abcdefgh") == False # Four mismatch pairs

assert solution.makePalindrome("zzzzzz") == True   # Uniform palindrome
assert solution.makePalindrome("azbycx") == False  # Three mismatch pairs

Test Case Summary

Test	Why
`"abcdba"`	Valid with one operation
`"aa"`	Already palindrome but requires allowed operations
`"abcdef"`	Too many mismatches
`"a"`	Smallest possible input
`"ab"`	Single mismatch pair
`"abc"`	Odd-length string
`"abba"`	Even-length palindrome
`"abcba"`	Odd-length palindrome
`"abca"`	Exactly one mismatch
`"abccaa"`	Exactly two mismatches
`"abcd"`	Two mismatches, still valid
`"abcde"`	Three mismatches
`"abcdefgh"`	Large mismatch count
`"zzzzzz"`	Repeated characters
`"azbycx"`	Multiple mismatch pairs

Edge Cases

Already Palindromic Strings

A common mistake is assuming that a string already being a palindrome means no operations are needed, therefore the answer should be false. However, the problem allows exactly one or two operations, and we can always preserve the palindrome structure while modifying characters.

For example:

"aa" can become "bb" in two operations.
"aba" can become "aca" in one operation by changing the middle character.

The implementation handles this naturally because zero mismatches still satisfies mismatches <= 2.

Odd-Length Strings

Odd-length strings contain a center character that has no mirrored partner. A naive implementation might incorrectly compare it against itself or mishandle pointer movement.

The solution avoids this issue by only running while left < right. The middle character is ignored automatically because it never affects palindrome symmetry.

Strings Requiring More Than Two Fixes

A major source of bugs is misunderstanding how many mismatches a single operation can repair. One operation can only modify one character, so it can only repair one mirrored mismatch pair.

For example:

"abcdef" has three mismatched pairs.
Even optimal character replacements cannot fix all pairs in only two operations.

The implementation correctly counts mismatch pairs independently and returns false whenever the count exceeds two.