Valid Palindrome

📋

Valid Palindrome

Edge cases:

</>

IDE

def isPalindrome(s: str) -> bool:public boolean isPalindrome(String s)bool isPalindrome(string s)function isPalindrome(s)

def isPalindrome(s: str) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean isPalindrome(String s) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

bool isPalindrome(string s) {
    // Write your solution here
    return false;
}

function isPalindrome(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseFailing to ignore non-alphanumeric characters, causing mismatch.✅ Add logic to skip non-alphanumeric characters before comparing.

Wrong: trueReturning true prematurely without checking all character pairs.✅ Continue checking until pointers cross; return false immediately on mismatch.

Wrong: falseNot handling empty string or single character as palindrome.✅ Return true if string length is 0 or 1.

Wrong: trueNot comparing characters case-insensitively.✅ Convert characters to lowercase before comparison.

Wrong: TLEUsing O(n^2) or extra string copies causing timeout on large inputs.✅ Use two-pointer approach with O(n) time and O(1) space.

✓

Test Cases

Try testing your code on empty and minimal inputs to catch base case bugs.

Consider tricky inputs with mixed characters and ensure your skipping logic is correct.

Focus on optimizing your solution to run in linear time without extra space.

t1_01basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Use two pointers starting from opposite ends of the string.

💡 Skip characters that are not alphanumeric and compare lowercase characters.

💡 Return false immediately if characters don't match; otherwise, continue until pointers cross.

Why it failed: Failed to ignore non-alphanumeric characters or case differences. Fix by skipping non-alphanumeric chars and comparing lowercase.

✓ Correctly handles skipping and case normalization.

t1_02basic

Input"race a car"

Expectedfalse

⏱ Performance - must finish in 2000ms

Ignoring spaces and case, the string is not a palindrome because 'e' != 'a' at mirrored positions.

💡 Check characters from opposite ends ignoring spaces and punctuation.

💡 Ensure to compare lowercase alphanumeric characters only.

💡 Return false as soon as a mismatch is found.

Why it failed: Incorrectly returns true despite mismatch. Fix by returning false immediately on first mismatch.

✓ Correctly detects non-palindromic strings.

t2_01edge

Input""

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty string is trivially a palindrome.

💡 Consider what happens when the string length is zero.

💡 Two pointers will cross immediately without mismatches.

💡 Return true for empty input as base case.

Why it failed: Fails on empty string input, possibly due to index errors. Fix by handling empty string as palindrome.

✓ Handles empty string correctly.

t2_02edge

Input"a"

Expectedtrue

⏱ Performance - must finish in 2000ms

Single character string is always a palindrome.

💡 Check behavior when string length is one.

💡 Two pointers start and end at same index, so no mismatch.

💡 Return true for single character strings.

Why it failed: Fails single character input, possibly due to incorrect pointer initialization. Fix by allowing pointers to meet or cross.

✓ Correctly handles single character strings.

t2_03edge

Input".,"

Expectedtrue

⏱ Performance - must finish in 2000ms

String with only non-alphanumeric characters is considered palindrome after ignoring them.

💡 Skip all non-alphanumeric characters before comparison.

💡 If no alphanumeric characters remain, treat as palindrome.

💡 Return true when string reduces to empty after filtering.

Why it failed: Fails to handle strings with only non-alphanumeric chars. Fix by skipping all such chars and returning true if none remain.

✓ Correctly handles strings with only non-alphanumeric characters.

t2_04edge

Input"0P"

Expectedfalse

⏱ Performance - must finish in 2000ms

Mixed alphanumeric with case difference; '0' != 'p' so not palindrome.

💡 Check that characters are compared case-insensitively.

💡 Ensure numeric and alphabetic characters are compared correctly.

💡 Return false if characters differ after case normalization.

Why it failed: Incorrectly returns true by ignoring case or character type differences. Fix by comparing lowercase alphanumeric characters exactly.

✓ Correctly distinguishes non-palindromic mixed alphanumeric strings.

t3_01corner

Input"ab@a"

Expectedtrue

⏱ Performance - must finish in 2000ms

Ignoring non-alphanumeric '@', string 'aba' is palindrome.

💡 Skip non-alphanumeric characters during comparison.

💡 Compare characters at pointers after skipping invalid chars.

💡 Return true if all valid characters match.

Why it failed: Fails by including non-alphanumeric characters in comparison. Fix by skipping them properly.

✓ Correctly skips non-alphanumeric characters.

t3_02corner

Input"abca"

Expectedfalse

⏱ Performance - must finish in 2000ms

String is not palindrome because 'b' != 'c' at mirrored positions.

💡 Check all pairs from opposite ends carefully.

💡 Return false immediately on first mismatch.

💡 Do not assume palindrome without full check.

Why it failed: Fails by returning true prematurely (greedy trap). Fix by checking all pairs until pointers cross.

✓ Correctly detects non-palindromes without premature acceptance.

t3_03corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Extra punctuation at the end ignored; still palindrome ignoring case and non-alphanumeric chars.

💡 Ensure to skip all non-alphanumeric characters including punctuation.

💡 Compare lowercase characters only.

💡 Return true if all valid characters match.

Why it failed: Fails by including trailing punctuation in comparison. Fix by skipping all non-alphanumeric chars.

✓ Correctly handles trailing punctuation.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000, solution must run in O(n) time within 2 seconds.

💡 Use two pointers to scan string once.

💡 Avoid extra space by skipping non-alphanumeric in-place.

💡 O(n) time complexity is required for large inputs.

Why it failed: Solution times out due to O(n^2) or extra copying. Fix by using two-pointer O(n) approach without extra string copies.

✓ Solution runs in O(n) time and passes performance constraints.

Practice

1. You are given an integer array and a target value. The task is to count the number of triplets in the array such that the sum of the triplet is less than the target. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use three nested loops to check all triplets and count those with sum less than target.

B. Sort the array, then for each element use two pointers to find pairs that form triplets with sum less than target.

C. Use dynamic programming to store counts of sums and build up to triplets.

D. Use a greedy approach by always picking the smallest elements first to form triplets.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting triplets with sum less than a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach that reduces complexity

   Sorting and using two pointers allows scanning pairs efficiently for each fixed element, reducing complexity from O(n^3) to O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + two pointers is a classic pattern for 3Sum variants [OK]

Hint: Sorting + two pointers reduces triple loops to quadratic [OK]

Common Mistakes:

• Assuming brute force is optimal
• Thinking DP applies directly here
• Believing greedy always works for sum constraints

2. Consider the following Python function implementing the optimal approach for counting triplets with sum smaller than target. What is the returned value when calling threeSumSmaller([-2, 0, 1, 3], 2)?

easy

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Sort input and initialize variables

   Sorted array is [-2, 0, 1, 3], count=0, n=4.

2. Step 2: Iterate and count triplets

   For i=0 (-2), check if sum of first three elements >= 2? -2+0+1= -1 < 2, continue. Use two pointers left=1, right=3. - curr_sum = -2 + 0 + 3 = 1 < 2 -> count += 3-1=2, left=2 - curr_sum = -2 + 1 + 3 = 2 not < 2 -> right=2 Now left=2, right=2 ends loop. For i=1 (0), sum of nums[1]+nums[2]+nums[3] = 0+1+3=4 >= 2 -> break loop. Total count=2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches expected output from example [OK]

Hint: Count increments by right-left when sum < target [OK]

Common Mistakes:

• Off-by-one in counting pairs
• Not breaking early when minimal sum >= target
• Misusing pointers leading to wrong counts

3. You are given an integer array and a target value. The task is to find all unique quadruplets in the array that sum up to the target. Which approach guarantees an optimal solution that balances time complexity and handles duplicates efficiently?

easy

A. Use four nested loops to check every quadruplet combination.

B. Use dynamic programming to build up solutions for smaller sums and combine them for quadruplets.

C. Apply a greedy algorithm that picks the largest elements first to reach the target sum quickly.

D. Sort the array, then use a hash map to store all pairs of sums and find complementary pairs without index overlap.

Solution

1. Step 1: Understand problem constraints

   Finding quadruplets summing to target requires checking combinations efficiently and avoiding duplicates.

2. Step 2: Evaluate approaches

   Brute force (four loops) is correct but inefficient. Greedy fails because sum combinations are not monotonic. DP is not suitable here. Hash map storing pairs of sums allows O(n^2) preprocessing and efficient lookup, handling duplicates by sorting and index checks.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map approach balances efficiency and correctness [OK]

Hint: Hash map of pairs enables efficient quadruplet search [OK]

Common Mistakes:

• Thinking greedy or DP solves 4Sum efficiently

4. Consider the following Python function implementing the optimal 4Sum approach. Given the input nums = [1, 0, -1, 0] and target = 0, what is the final returned list of quadruplets?

easy

A. [[-1, 0, 0, 1]]

B. [[0, 0, 0, 0]]

C. [[-1, -1, 1, 1]]

D. []

Solution

1. Step 1: Sort input and build two_sum_map

   Sorted nums = [-1, 0, 0, 1]. Pairs and sums: (-1,0)= -1, (-1,0)= -1, (-1,1)=0, (0,0)=0, (0,1)=1, (0,1)=1.

2. Step 2: Find complementary pairs summing to target=0

   Check sums and their complements: sum1=-1, sum2=1; sum1=0, sum2=0. Combine pairs ensuring no index overlap. Valid quadruplet is [-1,0,0,1].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only one quadruplet sums to zero without index overlap [OK]

Hint: Sort and check pairs sums carefully to find quadruplets [OK]

Common Mistakes:

• Confusing indices leading to duplicates or missing quadruplets

5. The following code attempts to implement the optimal 4Sum solution. Which line contains a subtle bug that can cause quadruplets with repeated indices to be included, violating problem constraints?

from typing import List
from collections import defaultdict

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    two_sum_map = defaultdict(list)
    res = set()
    for i in range(n):
        for j in range(i + 1, n):
            two_sum_map[nums[i] + nums[j]].append((i, j))
    for sum1 in two_sum_map:
        sum2 = target - sum1
        if sum2 not in two_sum_map:
            continue
        list1 = two_sum_map[sum1]
        list2 = two_sum_map[sum2]
        for (i, j) in list1:
            for (k, l) in list2:
                # BUG: Missing index overlap check
                quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))
                res.add(quad)
    return [list(quad) for quad in sorted(res)]

medium

A. Line that combines pairs into quadruplets without checking index overlap.

B. Line that appends pairs to two_sum_map.

C. Line that sorts the input array.

D. Line that returns the final list of quadruplets.

Solution

1. Step 1: Identify where index overlap is checked

   The code must ensure indices i,j,k,l are distinct to avoid repeated elements.

2. Step 2: Locate missing check

   The nested loops combining pairs lack any condition verifying indices are unique, allowing invalid quadruplets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing index overlap check causes subtle bug [OK]

Hint: Check index overlap before adding quadruplets [OK]

Common Mistakes:

• Forgetting index uniqueness check in pair combinations