Valid Palindrome IV solution and explanation
4 more videos on this problem
Leetcode 2330. Valid Palindrome IV - two-pointer methodCode-Yao · 6:47 · 267 views
2330. Valid Palindrome IV (Leetcode Medium)Programming Live with Larry · 4:28 · 256 views
LeetCode 1492: 2330. Valid Palindrome IV | Amazon Spring '23 High FrequencySoftware Interviews Prep · 6:33 · 149 views
LeetCode Valid Palindrome IV: A Step-by-Step Solution Tutorial | Leetcode 2330 | C++ SolutionNovice Coder · 8:07 · 129 views
2330. Valid Palindrome IVShuo Yan · 11:38 · 6 views
The 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.
Example 1:
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.
Example 2:
Input: s = "aa" Output: true Explanation: One way to make s a palindrome using 2 operations is: - Change s[0] to 'b'. Now, s = "ba". - Change s[1] to 'b'. Now, s = "bb". Two operations could be performed to make s a palindrome so return true.
Example 3:
Input: s = "abcdef" Output: false Explanation: It is not possible to make s a palindrome using one or two operations so return false.
Constraints:
1 <= s.length <= 105sconsists only of lowercase English letters.
Approach overview
Problem Overview: You are given a string s. The task is to determine whether it can become a palindrome after changing at most two characters. A palindrome reads the same forward and backward, so the key question is how many mirrored character pairs disagree.
Approach 1: Brute Force Character Replacement (Exponential)
A straightforward idea is to try all possible ways to modify up to two characters and check whether any resulting string becomes a palindrome. For each modified candidate, run a standard palindrome check using two pointers. While conceptually simple, the number of combinations grows quickly because each position can be changed to multiple characters. This approach has exponential branching and is impractical for longer strings. Time complexity is roughly O(26^2 * n) in simplified form, with O(n) space if new strings are created during modification.
Approach 2: Two Pointers Mismatch Count (O(n))
The optimal observation: a palindrome only cares about mirrored pairs. If s[i] and s[j] differ, you can fix that pair with one character change. Start two pointers at the beginning and end of the string and move inward. Every time the characters differ, increment a mismatch counter. If the counter exceeds two, forming a palindrome within two changes becomes impossible.
This works because each mismatch pair requires exactly one modification. For example, if s[i] != s[j], changing either character resolves that pair. Since the limit is two operations, the string can tolerate at most two mismatched mirrored pairs. The algorithm simply iterates once across half the string while comparing characters from both ends.
This implementation uses the two pointers pattern combined with simple string comparisons. The pointers move inward until they meet in the middle or the mismatch count exceeds two. Time complexity is O(n) because each character pair is examined once, and space complexity is O(1) since only a few counters and indices are used.
Recommended for interviews: Interviewers expect the two-pointer mismatch counting solution. It demonstrates recognition of palindrome symmetry and the ability to reduce the problem to pair comparisons. Mentioning the brute-force idea shows understanding of the problem constraints, but implementing the O(n) two-pointer scan proves algorithmic efficiency and familiarity with common string patterns.
Solution
We can use two pointers i and j, pointing to the beginning and end of the string, respectively, and then move towards the center, counting the number of different characters. If the number of different characters is greater than 2, return false; otherwise, return true.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the string s.
class Solution:
def makePalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
cnt = 0
while i < j:
cnt += s[i] != s[j]
i, j = i + 1, j - 1
return cnt <= 2class Solution {
public boolean makePalindrome(String s) {
int cnt = 0;
int i = 0, j = s.length() - 1;
for (; i < j; ++i, --j) {
if (s.charAt(i) != s.charAt(j)) {
++cnt;
}
}
return cnt <= 2;
}
}class Solution {
public:
bool makePalindrome(string s) {
int cnt = 0;
int i = 0, j = s.size() - 1;
for (; i < j; ++i, --j) {
cnt += s[i] != s[j];
}
return cnt <= 2;
}
};function makePalindrome(s: string): boolean {
let cnt = 0;
let i = 0;
let j = s.length - 1;
for (; i < j; ++i, --j) {
if (s[i] != s[j]) {
++cnt;
}
}
return cnt <= 2;
}func makePalindrome(s string) bool {
cnt := 0
i, j := 0, len(s)-1
for ; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
cnt++
}
}
return cnt <= 2
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Character Replacement | O(26^2 * n) | O(n) | Conceptual baseline to understand the effect of character modifications |
| Two Pointers Mismatch Count | O(n) | O(1) | Optimal approach for checking palindrome feasibility with limited edits |
Frequently asked questions
Is Valid Palindrome IV easy or hard?
Valid Palindrome IV is typically rated Medium. The implementation is short, but the key insight is realizing that each mismatched mirrored pair requires one change, so the string must have at most two mismatches.
Valid Palindrome IV Python/Java solution
The implementation is identical across languages. Initialize two indices at the start and end of the string, compare characters, and increment a mismatch counter when they differ. Stop early if mismatches exceed two. This logic translates directly to Python, Java, C++, Go, and TypeScript.
How to solve Valid Palindrome IV in O(n)?
Use two pointers starting at the beginning and end of the string. If characters differ, increment a mismatch counter because one change can fix that pair. Continue moving inward until the pointers meet. If mismatches are at most two, the string can be converted into a palindrome.
What is the best approach for Valid Palindrome IV?
The best approach uses the two pointers technique. Place one pointer at the start and one at the end of the string and compare characters while moving inward. Count mismatched pairs and ensure the count does not exceed two. This runs in O(n) time and O(1) space.
Is Valid Palindrome IV asked at Google/Amazon/Meta?
Palindrome and two-pointer string problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as Valid Palindrome II and edit-limited palindrome checks are common because they test pattern recognition and efficient string traversal.
What data structure is used in Valid Palindrome IV?
The problem primarily uses the two pointers technique on a string. No additional data structures like hash maps or stacks are required, which allows the solution to run with constant extra space.
What is the time complexity of Valid Palindrome IV?
The optimal solution runs in O(n) time where n is the length of the string. Each iteration compares a pair of characters using two pointers moving from both ends. Space complexity remains O(1) because only counters and indices are stored.