Valid Palindromic Sequence — Problem Statement & Solution Guide
Problem Description
Given a string s composed exclusively of lowercase English letters, determine whether it is possible to obtain a palindrome by removing at most one character from s. The algorithm must run in linear time relative to the length of the string. Return true if such a palindrome can be formed; otherwise, return false.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Valid Palindromic Sequence"
WHY DOES IT MATTER?
The two‑pointer pattern turns a potentially exponential search space into a deterministic linear scan, which is crucial for real‑time validation of user input, security tokens, or DNA sequences where latency matters.
OPTIMIZATION CHALLENGE
Recognizing that only the first mismatched pair matters reduces the problem from checking all O(n) deletions to just two constant‑time palindrome verifications, collapsing the complexity from O(n^2) to O(n).
REAL-WORLD CONNECTION
Think of a conveyor belt where items must be symmetric; when a mismatch appears, you can either discard the left or right item and continue checking symmetry, mirroring how load balancers drop a single outlier packet to maintain overall traffic balance.
During the interview, implement a helper that checks palindrome on a slice; when a mismatch is found, call it twice—once skipping left, once skipping right—and return the first true result. Keep the code short and avoid modifying the original string.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
When checking if a string can become a palindrome after removing at most one character, the naive solution would test every possible deletion, leading to O(n^2) time because each of the n positions would require a full palindrome scan. The optimal solution leverages the two‑pointer technique: one pointer starts at the left end and the other at the right, moving inward while characters match. Upon encountering the first mismatch, the problem reduces to checking whether either the substring obtained by skipping the left character or the one obtained by skipping the right character is a palindrome. Each of these checks is a simple linear scan, and because each character is examined at most twice, the overall runtime is O(n) with O(1) extra space. This greedy‑at‑first‑conflict strategy works because the constraint allows only a single deletion, so the first point of disagreement fully determines the only viable corrective actions, guaranteeing optimality without backtracking.
The two‑pointer paradigm is a cornerstone for many string‑processing problems (e.g., palindrome verification, reverse‑string in‑place, and partitioning). It avoids the overhead of auxiliary data structures and provides a clear, deterministic path through the input, which is essential for interview settings where both correctness and simplicity are evaluated. By converting a seemingly combinatorial problem into a constant‑choice decision at the first conflict, we achieve linear performance that scales to very large inputs, something a brute‑force approach cannot sustain.
Interview Questions on This Problem
Q1How would you modify the two‑pointer solution if the problem allowed removing at most two characters instead of one?
You would still use two pointers, but on a mismatch you would recursively explore both possibilities (skip left or skip right) and allow one more mismatch in the subsequent recursive call, effectively performing a depth‑limited search with at most two deletions, still bounded by O(n) because each branch scans at most the remaining substring.
Q2Why is it safe to return true as soon as one of the two skip‑checks yields a palindrome?
Because the problem permits at most one deletion; if either the left‑skipped or right‑skipped substring is a palindrome, we have found a valid way to achieve the goal, and any further checks cannot improve the answer, so early termination is both correct and optimal.
Q3In a distributed system processing massive strings, how could you parallelize the palindrome‑with‑one‑deletion check?
You can split the string into overlapping chunks that include the central region where a mismatch might occur; each node runs the two‑pointer scan on its segment, and a coordinator aggregates mismatch positions to decide whether a single deletion in the overlapping area can resolve the conflict, ensuring linear work overall while leveraging parallel I/O.
Examples
Input
abca
Output
true
Explanation: The original string is not a palindrome because the first and last characters differ (a vs a match, but b vs c differ). By deleting the character 'b' at index 1 we obtain "aca", which reads the same forward and backward. Hence the answer is true.
Input
racecar
Output
true
Explanation: The string already reads identically from both ends, so no deletion is required. Since zero deletions are allowed, the answer is true.
Input
abcdef
Output
false
Explanation: Any single‑character removal leaves a six‑character string with at most one matching pair, which cannot form a palindrome. Therefore it is impossible to achieve a palindrome with at most one deletion, so the answer is false.
Constraints
- 1 <= s.length <= 100000
- s consists only of characters 'a' through 'z'
- Time complexity must be O(|s|)
- Auxiliary space must be O(1)
Optimal Approach & Strategy
Use two pointers to find the first mismatch, then verify the two possible substrings (skip left or skip right) with a single linear scan, achieving O(n) time and O(1) extra space.
Brute Force Approach
Try deleting each character one by one and check if the resulting string is a palindrome; this requires O(n) deletions each costing O(n) to verify, leading to O(n^2) time.
Verified Code Solutions
/**
* Checks whether a substring s[l..r] is a palindrome.
* @param {string} s
* @param {number} l
* @param {number} r
* @return {boolean}
*/
function isPalindromeRange(s, l, r) {
while (l < r) {
if (s[l] !== s[r]) return false;
++l; --r;
}
return true;
}
/**
* Returns true if the string can become a palindrome after removing at most one character.
* @param {string} s
* @return {boolean}
*/
function validPalindrome(s) {
let i = 0, j = s.length - 1;
while (i < j) {
if (s[i] === s[j]) {
++i; --j;
} else {
return isPalindromeRange(s, i + 1, j) || isPalindromeRange(s, i, j - 1);
}
}
return true;
}
// Driver
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
if (input.length > 0) {
console.log(validPalindrome(input) ? "true" : "false");
}#include <bits/stdc++.h>
using namespace std;
bool isPalindromeRange(const string& s, int left, int right) {
while (left < right) {
if (s[left] != s[right]) return false;
++left; --right;
}
return true;
}
bool validPalindrome(const string& s) {
int i = 0, j = (int)s.size() - 1;
while (i < j) {
if (s[i] == s[j]) {
++i; --j;
} else {
// Skip either left or right character
return isPalindromeRange(s, i + 1, j) || isPalindromeRange(s, i, j - 1);
}
}
return true; // already palindrome
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
while (cin >> s) {
cout << (validPalindrome(s) ? "true" : "false") << "\n";
}
return 0;
}import java.util.*;
public class Main {
// Helper to check palindrome in s[l..r]
private static boolean isPalindromeRange(String s, int l, int r) {
while (l < r) {
if (s.charAt(l) != s.charAt(r)) return false;
l++; r--;
}
return true;
}
// Returns true if the string can become a palindrome after removing at most one character.
public static boolean validPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) == s.charAt(j)) {
i++; j--;
} else {
return isPalindromeRange(s, i + 1, j) || isPalindromeRange(s, i, j - 1);
}
}
return true; // already palindrome
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s = sc.next();
System.out.println(validPalindrome(s) ? "true" : "false");
}
sc.close();
}
}def valid_palindrome(s: str) -> bool:
"""Return True if s can become a palindrome after removing at most one character.
Uses a two‑pointer scan with O(n) time and O(1) extra space.
"""
def is_pal_range(l: int, r: int) -> bool:
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
i += 1
j -= 1
else:
# Skip either left or right character
return is_pal_range(i + 1, j) or is_pal_range(i, j - 1)
return True
if __name__ == "__main__":
import sys
s = sys.stdin.readline().strip()
print("true" if valid_palindrome(s) else "false")/**
* Checks whether a substring s[l..r] is a palindrome.
* @param {string} s
* @param {number} l
* @param {number} r
* @return {boolean}
*/
function isPalindromeRange(s, l, r) {
while (l < r) {
if (s[l] !== s[r]) return false;
++l; --r;
}
return true;
}
/**
* Returns true if the string can become a palindrome after removing at most one character.
* @param {string} s
* @return {boolean}
*/
function validPalindrome(s) {
let i = 0, j = s.length - 1;
while (i < j) {
if (s[i] === s[j]) {
++i; --j;
} else {
return isPalindromeRange(s, i + 1, j) || isPalindromeRange(s, i, j - 1);
}
}
return true;
}
// Driver
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
if (input.length > 0) {
console.log(validPalindrome(input) ? "true" : "false");
}Asked in Top Tech Interviews
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.