2330. Valid Palindrome IV

MediumTwo PointersString
Leetcode Link

Problem Description

You are given a 0-indexed string s made up of lowercase English letters. To address the problem, you are required to determine if the string s can be turned into a palindrome through exactly one or two operations. In this context, an operation is defined as changing any single character in the string s to any other character. The expected return value is a boolean true if it is possible to make s a palindrome with one or two changes, and false if it is not.

A palindrome is a string that reads the same forward and backward. For example, the strings "racecar" and "abba" are palindromes.

Intuition

The intuition behind the solution is straightforward. To check if a string is a palindrome, you compare characters from the outside in, meaning you compare the first and the last characters, the second and the second-to-last characters, and so on. If they're all the same, the string is a palindrome. However, this problem allows for one or two operations, meaning you are allowed to make up to two mismatches and still consider the string potentially a palindrome, as you can change one of the mismatching characters to match the other.

The solution approach, therefore, is to iterate over the string from both ends towards the center. If the characters in the corresponding positions don't match, we increment a counter. Since we are allowed up to two operations, we can tolerate up to two mismatches (incrementing the counter each time). If we finish the iteration and the counter is less than or equal to two, we return true. Otherwise, we return false.

The proposed solution does this efficiently by utilizing two pointers, i starting from the beginning of the string (0) and j from the end (len(s) - 1). With each iteration, these pointers move towards each other, and the comparison is made between s[i] and s[j]. The counting mechanism described above (cnt += s[i] != s[j]) increments cnt only when there's a mismatch. This process continues while i is less than j to ensure every character pair is checked exactly once.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Solution Approach

The implementation of the solution utilizes a simple yet effective two-pointer approach commonly used in array and string manipulation problems. Let's break down the steps, referring to the provided code solution:

  1. Initialize two pointers, i and j, where i starts at 0 (the beginning of the string s) and j starts at len(s) - 1 (the end of the string). These pointers will move towards the center of the string, comparing the characters at s[i] and s[j].

  2. Initialize a counter cnt to 0. This counter will keep track of the number of mismatches between the characters at the current pointers.

  3. Begin a while loop that runs as long as i < j. Since we are comparing characters from both ends of the string towards the center, the loop should terminate when the pointers meet or cross over.

  4. Inside the while loop, increment the counter cnt if the characters pointed by i and j are not the same, indicating a mismatch. The code does this with the line cnt += s[i] != s[j], which is a concise way of writing an if-else statement that increments cnt by 1 when the condition s[i] != s[j] is True.

  5. After checking for a mismatch, move the pointers closer to the center of the string: i moves right (i + 1), and j moves left (j - 1).

The data structures used here are elemental—the string s, the integer counter cnt, and the integer pointers i and j. There’s no need for more complex structures, as the problem is solved with direct access to string characters and simple arithmetic.

Finally, after exiting the while loop (meaning all the character pairs have been checked), evaluate the cnt counter. If it's less than or equal to 2, which means that zero, one, or two operations can turn s into a palindrome, then return true. Otherwise, if more than two mismatches were found, the string cannot be made into a palindrome with the allowed number of operations, so return false.

In summary, the algorithm's efficiency lies in its linear time complexity, O(n), where n is the length of the string s. It only traverses the string once and performs a constant amount of work at each step.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's consider a small example where the string s is "racebcr". According to the problem statement, we are allowed to use one or two operations to change any character to make s a palindrome.

  1. Initialize i = 0 and j = len(s) - 1, which is j = 6.
  2. Initialize the mismatch counter, cnt = 0.

We compare characters of s starting from the ends and moving towards the center:

  • Compare s[i] with s[j] (s[0] with s[6]), which are "r" and "r". They match, so cnt remains 0.
  • Move i to 1 and j to 5 and compare s[1] with s[5] ("a" with "c"). They don't match, so increment cnt to 1.
  • Move i to 2 and j to 4 and compare s[2] with s[4] ("c" with "b"). They don't match, so increment cnt to 2.
  • Move i to 3 and j to 3. Since i now equals j, we've reached the middle of the string.

At this point, the cnt equals 2, which is the maximum number of mismatches allowed for us to potentially be able to make the string a palindrome with one or two changes. Therefore, according to our algorithm, it is possible to make the string s a palindrome with two operations. Specifically, we could change the second character from "a" to "c" and the fifth character from "b" to "c" to make the string s into "racecar", which is a palindrome.

Hence, the function should return true for the input string "racebcr".

This walkthrough demonstrates how the two-pointer approach is used to efficiently determine if a string can be turned into a palindrome by changing one or two of its characters.

Solution Implementation

1class Solution:
2    def makePalindrome(self, s: str) -> bool:
3        # Initialize two pointers, left and right,
4        # to start from the beginning and end of the string, respectively.
5        left, right = 0, len(s) - 1
6
7        # Initialize a counter to keep track of non-matching character pairs.
8        mismatch_count = 0
9
10        # Iterate through the string until the two pointers meet or cross.
11        while left < right:
12            # If the characters at the current pointers do not match,
13            # increment the mismatch counter.
14            if s[left] != s[right]:
15                mismatch_count += 1
16
17            # Move the pointers closer to the center.
18            left += 1
19            right -= 1
20
21        # Return True if the number of non-matching pairs is less than or equal to 2.
22        # In such a case, by deleting or replacing up to one character,
23        # the string can be made into a palindrome.
24        return mismatch_count <= 2
25
1class Solution {
2    public boolean makePalindrome(String s) {
3        // Counter for the number of mismatches between characters
4        int mismatchCount = 0;
5        // Two pointers to compare characters from both ends of the string
6        int left = 0;
7        int right = s.length() - 1;
8
9        // Iterate over the string until the two pointers meet or cross
10        while (left < right) {
11            // Check if the characters at the current pointers do not match
12            if (s.charAt(left) != s.charAt(right)) {
13                // Increment the mismatch counter
14                ++mismatchCount;
15                // If mismatches are more than 1, it's not possible to make palindrome
16                // by changing just one character
17                if (mismatchCount > 1) {
18                    return false;
19                }
20            }
21            // Move the pointers towards the center
22            ++left;
23            --right;
24        }
25
26        // The string can be made into a palindrome if there's at most one mismatch
27        // because we can change one character to match the other
28        return true;
29    }
30}
31
1class Solution {
2public:
3    // Function to check if a string can be made palindrome by changing at most two characters
4    bool makePalindrome(string str) {
5        int mismatchCount = 0; // Counter for the number of mismatched character pairs
6        int left = 0;          // Left pointer starting from the beginning of the string
7        int right = str.size() - 1; // Right pointer starting from the end of the string
8
9        // Loop through the string until the left pointer meets or crosses the right pointer
10        while (left < right) {
11            // If the characters at the current pointers do not match
12            if (str[left] != str[right]) {
13                mismatchCount++; // Increment the mismatch counter
14            }
15
16            // Move the pointers closer towards the center of the string
17            left++;
18            right--;
19        }
20
21        // The string can be made palindrome if there are at most 2 mismatches (or none)
22        return mismatchCount <= 2;
23    }
24};
25
1function makePalindrome(s: string): boolean {
2    let mismatchCount = 0; // Initialize count of non-matching character pairs
3    let leftIndex = 0; // Start pointer for the left side of the string
4    let rightIndex = s.length - 1; // Start pointer for the right side of the string
5
6    // Loop from both ends of the string towards the center
7    while (leftIndex < rightIndex) {
8        // If characters at leftIndex and rightIndex do not match
9        if (s[leftIndex] !== s[rightIndex]) {
10            mismatchCount++; // Increment the count of mismatches
11        }
12        leftIndex++; // Move the left pointer towards the center
13        rightIndex--; // Move the right pointer towards the center
14    }
15
16    // A string can be made palindrome by changing at most one character,
17    // which might affect at most two of these character pairs (one at each end)
18    return mismatchCount <= 1;
19}
20
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

Time and Space Complexity

The provided code snippet checks if a given string can be transformed into a palindrome by modifying at most two characters.

Time Complexity:

The time complexity of the code is O(n) where n is the length of the input string s. This is because the while loop will iterate at most n/2 times (once for each pair of characters from the start and the end of the string until the middle is reached), performing constant time operations within each iteration.

Space Complexity:

The space complexity of the code is O(1) because the amount of extra space used does not depend on the size of the input string. The space used is constant as it only involves two index variables (i and j), and a counter variable (cnt).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫