How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Samsung.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Samsung during technical interviews.

Validate palindrome with constraints | Samsung Coding Question

Quick Overview

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.

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.

Input: (" ",)

Expected Output: True

Explanation: No alphanumeric characters; empty string is a palindrome.

Input: ("",)

Expected Output: True

Explanation: Empty string is trivially a palindrome (edge case).

Input: ("0P",)

Expected Output: False

Explanation: '0' != 'p'; digits and letters are both alphanumeric and must match.

Input: ("ab_a",)

Expected Output: True

Explanation: Underscore is non-alphanumeric and skipped; 'aba' is a palindrome.

Input: ("a.",)

Expected Output: True

Explanation: Single alphanumeric char after skipping '.'; a single character is a palindrome.

Input: ("Marge, let's send a sad Adena Mostradel sa, te g r2m",)

Expected Output: False

Explanation: After filtering, the digit '2' breaks the symmetry, so it 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.

Input: ("abc",)

Expected Output: False

Explanation: No single deletion makes it a palindrome.

Input: ("",)

Expected Output: True

Explanation: Empty string is a palindrome (edge case).

Input: ("a",)

Expected Output: True

Explanation: Single character is always a palindrome.

Input: ("deeee",)

Expected Output: True

Explanation: Delete the leading 'd' to get 'eeee'.

Input: ("ebcbbececabbacecbbcbe",)

Expected Output: True

Explanation: A near-palindrome resolvable with one skip on the correct side.

Input: ("abcdef",)

Expected Output: False

Explanation: Multiple mismatches; one deletion is insufficient.

Input: ("cbbcc",)

Expected Output: True

Explanation: Delete the trailing 'c' to get 'cbbc'.

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.

Quick Overview