Valid Palindrome IV - Practice Coding Problems

Valid Palindrome IV - 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcdba"

› Output: true

💡 Note: Compare from ends: a=a (match), b=b (match), c≠d (1 mismatch). Total mismatches = 1 ≤ 2, so return true.

Example 2 — Two Mismatches

$ Input: s = "aa"

› Output: true

💡 Note: Already a palindrome (0 mismatches), but we need exactly 1-2 operations. We can change any character to make 1 operation.

Example 3 — Too Many Mismatches

$ Input: s = "abcdef"

› Output: false

💡 Note: Compare pairs: a≠f, b≠e, c≠d. That's 3 mismatches > 2, so impossible with only 1-2 operations.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s that we want to make palindrome

Count Mismatches

Compare characters from both ends, count differences

Decision

Return true if ≤2 mismatches (can fix with 1-2 operations)

Key Takeaway

🎯 Key Insight: Count mismatches from both ends - if ≤2, we can make palindrome with 1-2 operations

Asked in

F Facebook 35 a Amazon 28 M Microsoft 22

The key insight is that to make a palindrome with 1-2 operations, we need at most 2 character mismatches when comparing from both ends. Best approach uses two pointers to count mismatches in O(n) time. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Count Mismatches	O(n)	O(1)	Use two pointers from ends to count character mismatches, check if ≤2
Brute Force - Try All Changes	O(n³)	O(n)	Try all possible 1-2 character changes and check if result is palindrome

Two Pointers - Count Mismatches — Algorithm Steps

Step 1: Initialize left pointer at start, right pointer at end
Step 2: Compare characters at both pointers, count mismatches
Step 3: Move pointers inward until they meet
Step 4: Return true if total mismatches ≤ 2

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Place pointers at both ends

Compare & Count

Count mismatches while moving pointers inward

Decision

Return true if mismatches ≤ 2

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s) {
    int left = 0, right = strlen(s) - 1;
    int mismatches = 0;
    
    while (left < right) {
        if (s[left] != s[right]) {
            mismatches++;
            if (mismatches > 2) {
                return false;
            }
        }
        left++;
        right--;
    }
    
    return true;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string with two pointers meeting in middle

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables and mismatch counter

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Count Mismatches — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler