2330. Valid Palindrome IV

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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.

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:

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].
Initialize a counter cnt to 0. This counter will keep track of the number of mismatches between the characters at the current pointers.
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.
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.
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.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

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.

Initialize i = 0 and j = len(s) - 1, which is j = 6.
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

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.

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

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don't know