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:

✅ 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: .

🤖 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 →