Valid Palindrome

🎯

Valid Palindrome

easyTWO_POINTERFacebookAmazonMicrosoft

Imagine you are building a text editor that needs to quickly check if a user's input is a palindrome ignoring punctuation and case, to enable fun palindrome-based features.

💡 This problem is about checking if a string reads the same forwards and backwards, ignoring non-alphanumeric characters and case. Beginners often struggle with handling these skips and case normalization while efficiently comparing characters.

📋

Problem Statement

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Return true if it is a palindrome, false otherwise.

1 ≤ length of s ≤ 10^5s consists of printable ASCII characters

💡

Example

Input"\"A man, a plan, a canal: Panama\""

Outputtrue

Ignoring non-alphanumeric characters and case, the string reads the same forwards and backwards.

Input"\"race a car\""

Outputfalse

Ignoring non-alphanumeric characters and case, the string is not the same forwards and backwards.

• "" (empty string) → true
• "a" (single character) → true
• ".," (only non-alphanumeric) → true
• "0P" (mixed alphanumeric, case) → false

⚠️

Common Mistakes

Not skipping non-alphanumeric characters properly

Incorrect palindrome result due to comparing punctuation or spaces

✅ Add checks to skip non-alphanumeric characters before comparing

Comparing characters without case normalization

Fails on inputs differing only by case, e.g. 'A' vs 'a'

✅ Convert characters to lowercase before comparison

Using reversed string without cleaning

False negatives due to punctuation or spaces included in reversed string

✅ Clean string before reversing or use two pointers skipping invalid chars

Off-by-one errors in pointer movement

Infinite loops or missed comparisons causing wrong results

✅ Carefully update pointers after comparisons and ensure loop conditions are correct

🧠

Brute Force (Clean and Reverse)

💡 This approach exists to build intuition by explicitly cleaning the string and then checking palindrome by reversing. It is simple but uses extra space and is less efficient.

Intuition

Remove all non-alphanumeric characters and convert to lowercase, then check if the cleaned string equals its reverse.

Algorithm

1. Initialize an empty string builder.
2. Iterate over the input string, appending only alphanumeric lowercase characters to the builder.
3. Create a reversed copy of the cleaned string.
4. Compare the cleaned string with its reversed copy; return true if they match, false otherwise.

💡 This algorithm is easy to understand but requires extra memory for the cleaned string and its reverse, which can be costly for large inputs.

</>

Code

def isPalindrome(s: str) -> bool:
    cleaned = []
    for ch in s:
        if ch.isalnum():
            cleaned.append(ch.lower())
    cleaned_str = ''.join(cleaned)
    reversed_str = cleaned_str[::-1]
    return cleaned_str == reversed_str

# Driver code
if __name__ == '__main__':
    test_cases = ["A man, a plan, a canal: Panama", "race a car"]
    for s in test_cases:
        print(f"Input: {s} -> Output: {isPalindrome(s)}")

Line Notes

cleaned = []Initialize a list to store filtered characters for efficient appends.

if ch.isalnum()Filter only alphanumeric characters to ignore punctuation and spaces.

cleaned.append(ch.lower())Convert to lowercase to ensure case-insensitive comparison.

reversed_str = cleaned_str[::-1]Create a reversed version of the cleaned string for palindrome check.

public class Solution {
    public static boolean isPalindrome(String s) {
        StringBuilder cleaned = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (Character.isLetterOrDigit(ch)) {
                cleaned.append(Character.toLowerCase(ch));
            }
        }
        String cleanedStr = cleaned.toString();
        StringBuilder reversedBuilder = new StringBuilder(cleanedStr);
        String reversedStr = reversedBuilder.reverse().toString();
        return cleanedStr.equals(reversedStr);
    }

    public static void main(String[] args) {
        String[] testCases = {"A man, a plan, a canal: Panama", "race a car"};
        for (String s : testCases) {
            System.out.println("Input: " + s + " -> Output: " + isPalindrome(s));
        }
    }
}

Line Notes

StringBuilder cleaned = new StringBuilder();Use StringBuilder for efficient string concatenation.

if (Character.isLetterOrDigit(ch))Filter only alphanumeric characters to ignore punctuation and spaces.

cleaned.append(Character.toLowerCase(ch));Convert to lowercase for case-insensitive comparison.

StringBuilder reversedBuilder = new StringBuilder(cleanedStr);Create a new StringBuilder from cleaned string to reverse without mutating original.

String reversedStr = reversedBuilder.reverse().toString();Reverse the cleaned string to compare for palindrome.

#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>

bool isPalindrome(const std::string& s) {
    std::string cleaned;
    for (char ch : s) {
        if (std::isalnum(ch)) {
            cleaned += std::tolower(ch);
        }
    }
    std::string reversed = cleaned;
    std::reverse(reversed.begin(), reversed.end());
    return cleaned == reversed;
}

int main() {
    std::string testCases[] = {"A man, a plan, a canal: Panama", "race a car"};
    for (const auto& s : testCases) {
        std::cout << "Input: " << s << " -> Output: " << (isPalindrome(s) ? "true" : "false") << std::endl;
    }
    return 0;
}

Line Notes

std::string cleaned;Create a new string to store filtered characters.

if (std::isalnum(ch))Check if character is alphanumeric to skip punctuation and spaces.

cleaned += std::tolower(ch);Convert to lowercase for case-insensitive comparison.

std::reverse(reversed.begin(), reversed.end());Reverse the cleaned string to check palindrome.

function isPalindrome(s) {
    let cleaned = '';
    for (let ch of s) {
        if (/[a-zA-Z0-9]/.test(ch)) {
            cleaned += ch.toLowerCase();
        }
    }
    let reversed = cleaned.split('').reverse().join('');
    return cleaned === reversed;
}

// Test cases
const testCases = ["A man, a plan, a canal: Panama", "race a car"];
for (const s of testCases) {
    console.log(`Input: ${s} -> Output: ${isPalindrome(s)}`);
}

Line Notes

let cleaned = '';Initialize an empty string to accumulate filtered characters.

if (/[a-zA-Z0-9]/.test(ch))Use regex to check if character is alphanumeric.

cleaned += ch.toLowerCase();Convert to lowercase for case-insensitive comparison.

let reversed = cleaned.split('').reverse().join('');Reverse the cleaned string to compare for palindrome.

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate over the string once to clean it (O(n)) and create a reversed copy (O(n)), so total O(n). Extra space is used for the cleaned string and its reverse, both O(n).

💡 For a string of length 100,000, this means about 200,000 operations and storing two copies of the string, which can be costly.

Interview Verdict: Accepted but not optimal

This approach works but uses extra memory and is slower than necessary; good for initial correctness but not ideal for large inputs.

🧠

Two Pointers (Skip Non-Alphanumeric)

💡 This approach improves efficiency by using two pointers from opposite ends, skipping non-alphanumeric characters on the fly, and comparing characters without extra space.

Intuition

Use two pointers starting at the beginning and end of the string, move inward skipping invalid characters, and compare characters case-insensitively.

Algorithm

1. Initialize two pointers: left at 0, right at end of string.
2. While left < right, move left forward if not alphanumeric, move right backward if not alphanumeric.
3. Compare characters at left and right pointers case-insensitively.
4. If mismatch, return false; if pointers cross, return true.

💡 This algorithm is efficient but requires careful pointer movement and character checks, which can be tricky to implement correctly at first.

</>

Code

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

# Driver code
if __name__ == '__main__':
    test_cases = ["A man, a plan, a canal: Panama", "race a car"]
    for s in test_cases:
        print(f"Input: {s} -> Output: {isPalindrome(s)}")

Line Notes

left, right = 0, len(s) - 1Initialize pointers at opposite ends of the string.

while left < right and not s[left].isalnum()Skip non-alphanumeric characters from the left.

while left < right and not s[right].isalnum()Skip non-alphanumeric characters from the right.

if s[left].lower() != s[right].lower()Compare characters case-insensitively to detect mismatch.

public class Solution {
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String[] testCases = {"A man, a plan, a canal: Panama", "race a car"};
        for (String s : testCases) {
            System.out.println("Input: " + s + " -> Output: " + isPalindrome(s));
        }
    }
}

Line Notes

int left = 0, right = s.length() - 1;Initialize two pointers at the start and end of the string.

while (left < right && !Character.isLetterOrDigit(s.charAt(left)))Skip non-alphanumeric characters from the left pointer.

while (left < right && !Character.isLetterOrDigit(s.charAt(right)))Skip non-alphanumeric characters from the right pointer.

if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))Compare characters ignoring case to detect mismatch.

#include <iostream>
#include <string>
#include <cctype>

bool isPalindrome(const std::string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        while (left < right && !std::isalnum(s[left])) {
            left++;
        }
        while (left < right && !std::isalnum(s[right])) {
            right--;
        }
        if (std::tolower(s[left]) != std::tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    std::string testCases[] = {"A man, a plan, a canal: Panama", "race a car"};
    for (const auto& s : testCases) {
        std::cout << "Input: " << s << " -> Output: " << (isPalindrome(s) ? "true" : "false") << std::endl;
    }
    return 0;
}

Line Notes

int left = 0, right = s.size() - 1;Initialize two pointers at the start and end of the string.

while (left < right && !std::isalnum(s[left]))Skip non-alphanumeric characters from the left pointer.

while (left < right && !std::isalnum(s[right]))Skip non-alphanumeric characters from the right pointer.

if (std::tolower(s[left]) != std::tolower(s[right]))Compare characters ignoring case to detect mismatch.

function isPalindrome(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        while (left < right && !/[a-zA-Z0-9]/.test(s[left])) {
            left++;
        }
        while (left < right && !/[a-zA-Z0-9]/.test(s[right])) {
            right--;
        }
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Test cases
const testCases = ["A man, a plan, a canal: Panama", "race a car"];
for (const s of testCases) {
    console.log(`Input: ${s} -> Output: ${isPalindrome(s)}`);
}

Line Notes

let left = 0, right = s.length - 1;Initialize two pointers at the start and end of the string.

while (left < right && !/[a-zA-Z0-9]/.test(s[left]))Skip non-alphanumeric characters from the left pointer.

while (left < right && !/[a-zA-Z0-9]/.test(s[right]))Skip non-alphanumeric characters from the right pointer.

if (s[left].toLowerCase() !== s[right].toLowerCase())Compare characters ignoring case to detect mismatch.

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the string once with two pointers, skipping invalid characters on the fly, so time is O(n). No extra space besides pointers is used, so space is O(1).

💡 For a string of length 100,000, this means about 100,000 operations and constant extra memory, making it very efficient.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its efficiency and minimal memory usage.

🧠

Two Pointers with Preprocessing (Clean then Two Pointers)

💡 This approach combines cleaning the string first and then using two pointers to check palindrome, balancing clarity and efficiency.

Intuition

First create a cleaned lowercase string with only alphanumeric characters, then use two pointers to compare characters from opposite ends.

Algorithm

1. Create a cleaned string containing only lowercase alphanumeric characters.
2. Initialize two pointers at the start and end of the cleaned string.
3. Move pointers inward comparing characters at each step.
4. Return false if mismatch found; otherwise true if pointers cross.

💡 This approach is easier to implement than skipping characters on the fly but uses extra space for the cleaned string.

</>

Code

def isPalindrome(s: str) -> bool:
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True

# Driver code
if __name__ == '__main__':
    test_cases = ["A man, a plan, a canal: Panama", "race a car"]
    for s in test_cases:
        print(f"Input: {s} -> Output: {isPalindrome(s)}")

Line Notes

cleaned = [ch.lower() for ch in s if ch.isalnum()]Create a list of lowercase alphanumeric characters to simplify comparisons.

left, right = 0, len(cleaned) - 1Initialize two pointers at the ends of the cleaned list.

if cleaned[left] != cleaned[right]Compare characters at pointers to detect mismatch.

left += 1; right -= 1Move pointers inward after successful comparison.

public class Solution {
    public static boolean isPalindrome(String s) {
        StringBuilder cleaned = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (Character.isLetterOrDigit(ch)) {
                cleaned.append(Character.toLowerCase(ch));
            }
        }
        int left = 0, right = cleaned.length() - 1;
        while (left < right) {
            if (cleaned.charAt(left) != cleaned.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String[] testCases = {"A man, a plan, a canal: Panama", "race a car"};
        for (String s : testCases) {
            System.out.println("Input: " + s + " -> Output: " + isPalindrome(s));
        }
    }
}

Line Notes

StringBuilder cleaned = new StringBuilder();Build a cleaned string with only lowercase alphanumeric characters.

if (Character.isLetterOrDigit(ch))Filter out non-alphanumeric characters.

if (cleaned.charAt(left) != cleaned.charAt(right))Compare characters at two pointers for mismatch.

left++; right--;Move pointers inward after successful comparison.

#include <iostream>
#include <string>
#include <cctype>

bool isPalindrome(const std::string& s) {
    std::string cleaned;
    for (char ch : s) {
        if (std::isalnum(ch)) {
            cleaned += std::tolower(ch);
        }
    }
    int left = 0, right = cleaned.size() - 1;
    while (left < right) {
        if (cleaned[left] != cleaned[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    std::string testCases[] = {"A man, a plan, a canal: Panama", "race a car"};
    for (const auto& s : testCases) {
        std::cout << "Input: " << s << " -> Output: " << (isPalindrome(s) ? "true" : "false") << std::endl;
    }
    return 0;
}

Line Notes

std::string cleaned;Create a new string to hold filtered lowercase characters.

if (std::isalnum(ch))Filter only alphanumeric characters.

if (cleaned[left] != cleaned[right])Compare characters at two pointers for mismatch.

left++; right--;Move pointers inward after successful comparison.

function isPalindrome(s) {
    const cleaned = [];
    for (const ch of s) {
        if (/[a-zA-Z0-9]/.test(ch)) {
            cleaned.push(ch.toLowerCase());
        }
    }
    let left = 0, right = cleaned.length - 1;
    while (left < right) {
        if (cleaned[left] !== cleaned[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Test cases
const testCases = ["A man, a plan, a canal: Panama", "race a car"];
for (const s of testCases) {
    console.log(`Input: ${s} -> Output: ${isPalindrome(s)}`);
}

Line Notes

const cleaned = [];Initialize an array to store filtered lowercase characters.

if (/[a-zA-Z0-9]/.test(ch))Use regex to filter alphanumeric characters.

if (cleaned[left] !== cleaned[right])Compare characters at two pointers for mismatch.

left++; right--;Move pointers inward after successful comparison.

⏱

Complexity

TimeO(n)

SpaceO(n)

We first create a cleaned string of length up to n, then use two pointers to check palindrome in O(n). Extra space is O(n) for the cleaned string.

💡 For input length 100,000, this means about 200,000 operations and storing one extra string of length up to 100,000.

Interview Verdict: Accepted and clear

This approach is a good balance between clarity and efficiency, often preferred if interviewer allows extra space.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the two pointers skipping non-alphanumeric characters approach is best to code due to its optimal time and space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Clean and Reverse)	O(n)	O(n)	No	N/A	Mention only - never code
2. Two Pointers (Skip Non-Alphanumeric)	O(n)	O(1)	No	N/A	Code this approach
3. Two Pointers with Preprocessing	O(n)	O(n)	No	N/A	Good alternative if interviewer allows extra space

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying requirements, then explain brute force, and progressively optimize. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem requirements and constraints.Step 2: Present the brute force approach by cleaning and reversing the string.Step 3: Explain the two pointers approach skipping invalid characters.Step 4: Code the optimal two pointers solution with skipping.Step 5: Test with edge cases and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your ability to handle string manipulation, pointer logic, edge cases, and optimize space/time complexity.

Common Follow-ups

• What if the string is extremely large? → Use two pointers with O(1) space.
• Can you handle Unicode characters? → Adjust alphanumeric checks accordingly.

💡 These follow-ups test your ability to optimize and handle real-world input variations.

🔍

Pattern Recognition

When to Use

1) Need to check palindrome or symmetric property; 2) String or array input; 3) Ignoring certain characters or conditions; 4) Can use two pointers from opposite ends.

Signature Phrases

"ignoring non-alphanumeric characters""case-insensitive palindrome check"

NOT This Pattern When

Problems that require counting palindromic subsequences or dynamic programming for palindrome partitioning

Similar Problems

Palindrome Permutation - checks if any permutation can form a palindromeLongest Palindromic Substring - finds longest palindrome substring using two pointers

Practice

1. Given the following code snippet and inputs, what is the final state of nums1 after the merge function completes?

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

nums1 = [2,5,7,0,0,0]
m = 3
nums2 = [1,3,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)

easy

A. [1,2,3,6,5,7]

B. [1,3,5,6,7,7]

C. [2,3,5,6,7,0]

D. [1,2,3,5,6,7]

Solution

1. Step 1: Trace last elements comparison

   Compare nums1[2]=7 and nums2[2]=6, place 7 at nums1[5], decrement i and k.

2. Step 2: Continue merging backwards

   Next compare nums1[1]=5 and nums2[2]=6, place 6 at nums1[4], decrement j and k. Then place 5, 3, 2, 1 accordingly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Final merged array is sorted and contains all elements [OK]

Hint: Merge from back preserves order and fills nums1 correctly [OK]

Common Mistakes:

• Off-by-one errors in indices
• Not copying remaining nums2 elements

2. Consider the following code snippet for removing duplicates from a sorted array allowing at most two duplicates. What is the value of write_index after processing the input [1,1,2]?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace write_index and read_index for input [1,1,2]

   Initially, write_index=0. Iteration 0: write_index<2, write 1, write_index=1. Iteration 1: write_index=1<2, write 1, write_index=2. Iteration 2: nums[2]=2 != nums[0]=1, write 2, write_index=3.

2. Step 2: Final write_index value

   After processing all elements, write_index=3, indicating the length of the modified array.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All elements allowed, write_index matches array length [OK]

Hint: write_index increments for allowed duplicates [OK]

Common Mistakes:

• Off-by-one errors in write_index
• Confusing read_index with write_index
• Not handling first two elements separately

3. Given a sorted array of integers (which may include negatives), you need to return a new array containing the squares of each number, also sorted. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Traverse the array once, square elements in place, and rely on the input being sorted to keep the order.

B. Square each element and then sort the resulting array using a standard sorting algorithm.

C. Use a dynamic programming approach to build the squared array based on previous computations.

D. Use two pointers starting at both ends of the array, compare absolute values, and fill the output array from the end.

Solution

1. Step 1: Understand the problem constraints

   The input array is sorted but contains negative numbers, so squaring can disrupt order.

2. Step 2: Identify the approach that leverages sorted input

   Two pointers from both ends compare absolute values and fill the output array from the end, ensuring sorted squares in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two-pointer approach uses input order optimally [OK]

Hint: Two pointers from ends handle negatives optimally [OK]

Common Mistakes:

• Assuming squaring preserves order
• Using sorting after squaring without leveraging input order
• Confusing DP with this problem

4. You are given an array representing heights of bars where water can be trapped between bars after raining. Which approach guarantees an optimal O(n) time and O(1) space solution to calculate the total trapped water?

easy

A. Use two pointers starting from opposite ends, updating left_max and right_max while moving inward.

B. Use a greedy approach that always fills the lowest bar first without considering future bars.

C. Use dynamic programming with a 2D table storing water trapped between every pair of bars.

D. Use a brute force nested loop to find max heights on left and right for each bar.

Solution

1. Step 1: Understand problem constraints

   The problem requires calculating trapped water efficiently in linear time and constant space.

2. Step 2: Identify approach matching constraints

   The two pointers approach moves inward from both ends, updating left_max and right_max, allowing O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers approach is known optimal for trapping rain water [OK]

Hint: Two pointers from ends -> O(n) time, O(1) space [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing DP with 2D tables for this problem
• Thinking greedy fill lowest bar always works

5. If the problem is changed so that duplicates are allowed at most k times (where k is a positive integer), which modification to the optimal two-pointer approach is correct?

hard

A. Change the condition to compare current element with the element at write_index - k and allow writing if different

B. Use a hash map to count occurrences and rebuild the array with at most k duplicates

C. Keep the original condition comparing with write_index - 2 regardless of k

D. Use nested loops to remove duplicates exceeding k by shifting elements

Solution

1. Step 1: Understand the generalization

   Allowing at most k duplicates means we must check if the current element differs from the element k positions before the write pointer.

2. Step 2: Modify the condition accordingly

   Replace the fixed 2 with k in the condition: write_index < k or nums[read_index] != nums[write_index - k]. This generalizes the approach.

3. Step 3: Avoid inefficient or incorrect methods

   Hash maps or nested loops increase time or space complexity unnecessarily.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Condition generalized to k duplicates ensures correctness and efficiency [OK]

Hint: Replace 2 with k in index offset check [OK]

Common Mistakes:

• Not generalizing condition to k
• Using hash maps increases space
• Nested loops cause O(n²) time