Flexible Palindrome — Problem Statement & Solution Guide

Two PointersEasyTwo Pointers

TimeO(n)

SpaceO(1)

Problem Description

Given a string s, decide whether it can become a palindrome after deleting at most one character. Return true if such a deletion exists, otherwise return false. The input consists of a single string s. The output is a boolean value expressed as the words true or false.

DSA Pattern Breakdown

"Flexible Palindrome"

easy

WHY DOES IT MATTER?

The two‑pointer pattern reduces the search space dramatically by eliminating the need to generate all possible deletions, which is crucial for time‑critical systems that process large strings in real time.

OPTIMIZATION CHALLENGE

The key insight is that a single mismatch can only be resolved by removing one of the two offending characters, so only two palindrome checks are necessary instead of n possibilities.

REAL-WORLD CONNECTION

In distributed log replication, a node may need to verify that a log segment is consistent after dropping at most one corrupted entry; the two‑pointer scan is analogous to a fast consistency check that only examines boundary mismatches.

When implementing, avoid creating substrings; instead, compare characters directly using indices to keep space usage constant and prevent hidden O(n) allocations.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks whether a string can become a palindrome after removing at most one character. A naive approach would try deleting each character and checking palindrome, leading to O(n^2) time. The optimal solution uses the two‑pointer technique: start pointers at both ends, move inward while characters match; when a mismatch occurs, we only need to test the two substrings obtained by skipping either the left or right character. If either substring is a palindrome, the answer is true. This runs in O(n) time and O(1) space.

Interview Questions on This Problem

Q1What is the time complexity of the optimal solution for Flexible Palindrome and why is it efficient for large inputs?

The optimal solution runs in O(n) time because it scans the string once with two pointers and performs at most two additional palindrome checks, each linear in the remaining substring. This linear time complexity is efficient for large inputs compared to the O(n^2) naive approach.

Q2How would you modify the algorithm if the string could contain Unicode characters that are represented by surrogate pairs in UTF-16?

Treat the string as a sequence of Unicode code points rather than UTF-16 code units. In languages like JavaScript, use Array.from(s) to get an array of code points, then apply the two‑pointer algorithm on that array to avoid miscounting surrogate pairs.

Q3During an interview, a candidate mistakenly returns true for the input "abca". What is the flaw in their logic?

They likely only checked the left deletion path (removing 'b') and assumed it suffices. However, "aca" is a palindrome, but the algorithm must also consider the right deletion path (removing 'c') and ensure that at most one deletion is allowed. The candidate’s logic missed the case where the mismatch occurs at the right side.

Examples

Example 1

Input

abca

Output

true

Explanation: Compare characters from both ends: a==a, b!=c. Removing the character at index 1 (b) yields "aca", which reads the same forwards and backwards. Thus the answer is true.

Example 2

Input

abc

Output

false

Explanation: a!=c at the ends. Removing a gives "bc" (not a palindrome), removing b gives "ac" (not a palindrome), and removing c gives "ab" (not a palindrome). No single deletion works, so the answer is false.

Example 3

Input

deeee

Output

true

Explanation: The string is already a palindrome; no deletion is needed. Therefore the answer is true.

Example 4

Input

abcdba

Output

true

Explanation: a==a, b==b, c!=d. Removing the character at index 2 (c) gives "abdba", which is a palindrome. Hence the answer is true.

Example 5

Input

abccba

Output

true

Explanation: The string reads the same forwards and backwards, so it is already a palindrome. The answer is true.

Constraints

1 <= s.length <= 100000
s consists only of lowercase English letters

Optimal Approach & Strategy

Use two pointers to scan from both ends; on a mismatch, test the two possible single‑character deletions by checking if the remaining substring is a palindrome. This achieves O(n) time and O(1) space.

Brute Force Approach

Try deleting each character one by one and check if the resulting string is a palindrome. This requires O(n^2) time and O(n) space for the temporary strings.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function flexiblePalindrome(s) {
  if (s.length < 2) return true;
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] === s[right]) {
      left++;
      right--;
    } else {
      return s[left + 1] === s[right] || s[left] === s[right - 1] ? true : false;
    }
  }
  return true;
}

#include <string>
using namespace std;

class Solution {
public:
    bool isPalindromeRange(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

    bool flexiblePalindrome(string s) {
        int left = 0, right = (int)s.length() - 1;
        while (left < right) {
            if (s[left] == s[right]) {
                left++;
                right--;
            } else {
                return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
            }
        }
        return true;
    }
};

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return s.substring(left + 1, right + 1).equals(new StringBuilder(s.substring(left + 1, right + 1)).reverse().toString()) || s.substring(left, right + 1).equals(new StringBuilder(s.substring(left, right + 1)).reverse().toString());
            }
            left++;
            right--;
        }
        return true;
    }
}

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return s[left + 1:right + 1] == s[left + 1:right + 1][::-1] or s[left:right] == s[left:right][::-1]
        left += 1
        right -= 1
    return True

function flexiblePalindrome(s) {
  if (s.length < 2) return true;
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] === s[right]) {
      left++;
      right--;
    } else {
      return s[left + 1] === s[right] || s[left] === s[right - 1] ? true : false;
    }
  }
  return true;
}

Asked in Top Tech Interviews

SwiggyZomato

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Flexible Palindrome Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Flexible Palindrome — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor