Validate palindrome with constraints
Company: Samsung
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string s, return true if s reads the same forward and backward after removing all non-alphanumeric characters and ignoring letter case. Implement an O
(n)-time, O(
1)-extra-space solution using two pointers. Follow-ups:
(a) Modify your solution to return true if s can become a palindrome after deleting at most one character;
(b) Discuss how you would support full Unicode (e.g., combining marks and non-ASCII letters);
(c) Provide test cases and analyze complexity.
Quick Answer: This question evaluates a candidate's ability to implement string-processing algorithms and two-pointer techniques under O(n) time and O(1) extra space constraints, including character filtering, case normalization, edge-case handling, and algorithmic complexity analysis.
Valid Palindrome
Given a string `s`, return `true` if `s` reads the same forward and backward after removing all non-alphanumeric characters and ignoring letter case; otherwise return `false`.
An empty string (or one with no alphanumeric characters) is considered a valid palindrome.
Use the two-pointer technique to achieve O(n) time and O(1) extra space (no building of a new filtered string).
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After filtering and lowercasing, the string is "amanaplanacanalpanama", which is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: After filtering, "raceacar" is not a palindrome.
Example 3:
Input: s = " "
Output: true
Explanation: After filtering, the string is empty, which is a palindrome.
Constraints
- 1 <= s.length <= 2 * 10^5
- s consists only of printable ASCII characters.
- Comparison is case-insensitive and ignores all non-alphanumeric characters.
Examples
Input: ("A man, a plan, a canal: Panama",)
Expected Output: True
Explanation: Filtered/lowercased: 'amanaplanacanalpanama' is a palindrome.
Input: ("race a car",)
Expected Output: False
Explanation: Filtered: 'raceacar' is not a palindrome.
Hints
- Place one pointer at the start and one at the end of the string.
- Advance each pointer past any non-alphanumeric character before comparing.
- Compare the lowercased characters at the two pointers; if they ever differ, it is not a palindrome.
- Filtering in place with two pointers keeps the extra space at O(1) — avoid building a cleaned copy of the string.
Valid Palindrome II (delete at most one character)
Follow-up (a). Given a string `s`, return `true` if `s` can be made a palindrome after deleting **at most one** character from it; otherwise return `false`.
For this variant, treat the input as already containing only the characters that matter — compare characters directly (case-sensitive, no filtering). The goal is to demonstrate the two-pointer technique with a single allowed mismatch.
When the two pointers disagree, you have exactly two choices: skip the left character or skip the right character. The string is a near-palindrome if either remaining substring is a palindrome.
Example 1:
Input: s = "aba"
Output: true
Explanation: Already a palindrome; zero deletions needed.
Example 2:
Input: s = "abca"
Output: true
Explanation: Delete 'c' to get "aba".
Example 3:
Input: s = "abc"
Output: false
Explanation: No single deletion yields a palindrome.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
- At most one character may be deleted.
Examples
Input: ("aba",)
Expected Output: True
Explanation: Already a palindrome; zero deletions needed.
Input: ("abca",)
Expected Output: True
Explanation: Delete 'c' (or 'b') to get a palindrome.
Hints
- Walk two pointers inward; while characters match, this part is already palindromic.
- At the first mismatch you are allowed one deletion: try skipping the left character OR the right character.
- Write a helper that checks whether a substring s[lo..hi] is a plain palindrome.
- Return true if either s[i+1..j] or s[i..j-1] is a palindrome after the single mismatch.