Problem

You are given a 0-indexed string s consisting of only lowercase English letters. In one operation, you can change any character of s to any other character.

Return true if you can make s a palindrome after performing exactly one or two operations, or return false otherwise.

Examples

Example 1:

1
2
3
4
5

Input: s = "abcdba"
Output: true
Explanation: One way to make s a palindrome using 1 operation is:
- Change s[2] to 'd'. Now, s = "abddba".
One operation could be performed to make s a palindrome so return true.

Solution

Method 1 - Using Two Pointer Technique

To determine if a string can be made into a palindrome with exactly one or two operations, we need to count the number of mismatches between the characters when the string is read from the beginning and the end. For a string to be transformed into a palindrome with one or two operations, the number of mismatches should be no more than 2.

Approach

  1. Use two pointers, one starting from the beginning (left) and the other from the end (right) of the string.
  2. Count the number of mismatches while traversing from both ends towards the center.
  3. If the number of mismatches is less than or equal to 2, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {
    public boolean makePalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        int mismatches = 0;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                mismatches++;
                if (mismatches > 2) {
                    return false;
                }
            }
            left++;
            right--;
        }

        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def makePalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        mismatches = 0
        
        while left < right:
            if s[left] != s[right]:
                mismatches += 1
                if mismatches > 2:
                    return False
            left += 1
            right -= 1
        
        return True

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string.
  • 🧺 Space complexity: O(1) for using a constant amount of space for the mismatch counter.