Skip to main content
Talentd

Valid Palindrome IV - Solution & Explanation

MediumPremiumFree on FleetCodeTwo PointersString6 min readAsked at: Amazon, Meta
Practice this problem

Problem Statement

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 <= 105
  • s consists 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Character ReplacementO(26^2 * n)O(n)Conceptual baseline to understand the effect of character modifications
Two Pointers Mismatch CountO(n)O(1)Optimal approach for checking palindrome feasibility with limited edits

Video Solution

Leetcode 2330. Valid Palindrome IV - two-pointer method • Code-Yao • 267 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Valid Palindrome IV with our built-in code editor and test cases.

Practice on FleetCode
Previous

Valid Palindrome

Next

Valid Palindrome II