easy Valid Palindrome

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: sentence = "A man, a plan, a canal, Panama!"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: sentence = "Was it a car or a cat I saw?"
Output: true
Explanation: Explanation: "wasitacaroracatisaw" is a palindrome.

Constraints:

1 <= s.length <= 2 * 10⁵
s consists only of printable ASCII characters.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Valid Palindrome — problem

1. Why / judgment

Phrase palindrome after filtering non-alphanumeric and ignoring case. Two pointers from ends with skip logic — not reverse full cleaned string only (that is O(n) space fine, but two pointers show in-place judgment).

2. Big-O derivation (K11)

O(n) time O(1) extra two-pointer (O(n) if build cleaned).
Must not use O(n²) string rebuild naively in some langs.

3. Pattern + when-NOT (K12)

Name: TWO POINTERS + FILTER PREDICATE

Recognition: is palindrome under alnum/case rules.

When-NOT: Exact string palindrome no filter → simpler. Palindrome permutation → counts not two pointers. Valid palindrome II (one delete) → greedy mismatch branch.

4. Edge hand-run (K13)

empty / only symbols → true.
single alnum true.
"A man, a plan, a canal: Panama" true.

5. Interviewer follow-ups (model answers)

Q1. Unicode letters?
A: Define isalnum per locale/problem (usually ASCII).

Q2. Why two pointers vs reverse?
A: O(1) extra; same time; shows pointer skill.

Q3. Case fold?
A: tolower both sides.

6. Short drills

Drill: "race a car" false.
Drill: implement Valid Palindrome II next.

✅ Solution Valid Palindrome

Problem Statement

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: sentence = "A man, a plan, a canal, Panama!"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: sentence = "Was it a car or a cat I saw?"
Output: true
Explanation: Explanation: "wasitacaroracatisaw" is a palindrome.

Example 3:

Input: sentence = "race a car"
Output: false
Explanation: Explanation: "raceacar" is not a palindrome.

Constraints:

1 <= s.length <= 2 * 10⁵
s consists only of printable ASCII characters.

Solution

This problem aims to check if a given string is a palindrome. A palindrome is a word, phrase, number, or other sequences of characters that read the same forward and backward, ignoring spaces, punctuation, and capitalization. Our algorithm can leverage the two-pointer technique where one pointer starts at the beginning of the string, and the other one starts at the end. The two pointers move towards each other, checking if the characters they point to are the same.

Walkthrough of the algorithm

Let's take a detailed walkthrough of the code:

The isPalindrome function starts by setting two pointers: 'i' at the start of the string and 'j' at the end.
Then it enters a while loop which continues until the two pointers cross each other. Inside this loop:
- The first inner while loop moves 'i' forward, skipping any characters that are not letters or digits, until it points to a valid character or it crosses 'j'.
- The second inner while loop moves 'j' backward, skipping any characters that are not letters or digits, until it points to a valid character or it crosses 'i'.
After finding valid characters at 'i' and 'j', it converts these characters to lowercase and checks if they're the same.
- If they're not the same, the function immediately returns false since the string can't be a palindrome if these characters are different.
- If they are the same, 'i' is incremented and 'j' is decremented, and the loop continues to the next pair of characters.
If the while loop completes without finding any unequal pairs of characters, the function returns true, indicating that the string is a palindrome.

Code

Here is the code for this algorithm:

java

class Solution {

  public boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1; // initialize two pointers, one at the start and one at the end of the string
    while (i < j) { // continue until the two pointers cross over
      while (i < j && !Character.isLetterOrDigit(s.charAt(i))) { // move i forward until a letter or digit is found
        i++;
      }
      while (i < j && !Character.isLetterOrDigit(s.charAt(j))) { // move j backward until a letter or digit is found
        j--;
      }

      // compare the characters at i and j after converting them to lowercase
      if (
        Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))
      ) return false; // if they are not equal, the string is not a palindrome
      i++; // move i forward
      j--; // move j backwards
    }

    return true; // if the two pointers have crossed over, the string is a palindrome
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Test case 1: "A man, a plan, a canal, Panama!"
    // Expected output: true
    System.out.println(sol.isPalindrome("A man, a plan, a canal, Panama!"));

    // Test case 2: "race a car"
    // Expected output: false
    System.out.println(sol.isPalindrome("race a car"));

    // Test case 3: "Was it a car or a cat I saw?"
    // Expected output: true
    System.out.println(sol.isPalindrome("Was it a car or a cat I saw?"));

    // Test case 4: "Madam, in Eden, I'm Adam."
    // Expected output: true
    System.out.println(sol.isPalindrome("Madam, in Eden, I'm Adam."));

    // Test case 5: "empty string"
    // Expected output: true
    System.out.println(sol.isPalindrome(""));
  }
}

Complexity Analysis

Time Complexity

Two-pointer traversal: The algorithm uses two pointers, i starting from the left and j from the right, and moves them inward toward each other. The loop runs until the two pointers meet or cross over, meaning we traverse the string once. This results in a time complexity of , where N is the length of the input string.
Nested loops (for skipping non-alphanumeric characters):
- Within the main loop, we use two while loops to skip non-alphanumeric characters. Each of these inner loops also runs at most N times in total, as each character is only skipped once. Even though the loops are nested, their total number of iterations is still proportional to the size of the string.
Character comparisons: Each valid alphanumeric character is compared after converting to lowercase, which is a constant time operation, .

Overall time complexity: .

Space Complexity

Constant space: The algorithm only uses a few extra variables (i, j) and performs character operations in place. No additional data structures are used that scale with the input size.

Overall space complexity: .

🎯 STRICT STANDOUT — Solution Valid Palindrome

1. Why / judgment

while lo

2. Big-O derivation (K11)

O(n).
Trace Panama classic true.
Trace "0P" careful: '0' alnum 'P' alnum mismatch if casefold only letters — 0 vs p false.

3. Pattern + when-NOT (K12)

Name: TWO POINTER FILTERED COMPARE

Recognition: valid palindrome phrase.

When-NOT: Build cleaned then check — OK alternate.

4. Edge hand-run (K13)

all skipped chars.
numeric palindrome "12321".

5. Interviewer follow-ups (model answers)

Q1. isalnum include digits?
A: Yes per LC.

Q2. Surrogate pairs?
A: Language dependent.

Q3. Early exit?
A: On first mismatch.

6. Short drills

Drill: " ", "a.", "ab_a".
Drill: contrast with reverse(cleaned).

🧩 Pattern · Two Pointers

Recognize it: A sorted array where you need a pair/triplet or an in-place partition → walk two indices inward.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Valid Palindrome? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Valid Palindrome** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Valid Palindrome** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Valid Palindrome**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Valid Palindrome**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Find the Difference Rank Transform of an Array →