Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-013 · FOCUSED PRACTICE

Valid Palindrome

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 55998 deterministic checks. Learner drafts are not executed.

Understand the problem

Determine whether the ASCII letters and digits of a string form a palindrome after folding ASCII uppercase letters to lowercase.

  • s is non-null with 0–100,000 UTF-16 code units. Eligible symbols are exactly A–Z, a–z, and 0–9; every other code unit is ignored, including accented letters, combining marks, and both halves of supplementary characters.
  • ASCII uppercase is folded by its fixed A–Z offset. This is deliberately an ASCII predicate, not Unicode normalization, locale-sensitive case folding, or a human-language palindrome definition.
  • Return true when the filtered sequence reads the same in both directions. Empty or punctuation-only input is true. Do not modify s or allocate a filtered copy in the optimized method.

Examples

  1. Input: "A man, a plan, a canal: Panama"
    Output: true

    After ASCII filtering and folding, the sequence is amanaplanacanalpanama.

  2. Input: "éaBé"
    Output: false

    The accented characters are ignored; the remaining a and b mismatch.

Before you start

  • Array indexing and inclusive pointer bounds
  • Loop invariants and Java value versus reference semantics

Recognize the structure

Only the next eligible symbol on each end matters. Ignorable symbols can be skipped without constructing a new sequence. Define eligibility before choosing char-level pointers.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

No unsaved text changes · 88/20,000 characters

Self-review

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Write the exact eligible alphabet first.

Hint 2

Can you find the next retained symbol without storing it?

Hint 3

Skip ignored endpoints, compare folded symbols, then move inward.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Filter and reverse

Append eligible symbols in folded form, then compare the buffer to its reversal. "A,b,a!" becomes "aba" and reverses to "aba"; "0P" becomes "0p" and reverses to "p0". This takes O(n) time and O(n) extra space; it provides an easy specification for the constant-space scan.

Improve the baseline

Separate eligibility and equality

Skipping punctuation is different from matching case. Write an explicit ASCII predicate and a fold that changes uppercase letters only.

Find comparable ends

If the left code unit is ineligible, increment left. Otherwise, if the right is ineligible, decrement right. Only compare when both qualify.

Consume a matched pair

A mismatch returns false immediately; a match moves both pointers inward. Crossing or meeting leaves at most one eligible center, which always matches itself.

Why it is correct

Matched exterior

At each loop boundary, every eligible symbol outside [left,right] has been matched to the corresponding eligible symbol at the opposite end.

Safe skip and rejection

Skipping an ineligible code unit removes nothing from the filtered sequence. Unequal eligible endpoints cannot be repaired by inner symbols, so a mismatch proves failure.

Termination and success

Every iteration moves at least one pointer or returns. At left>=right no unmatched opposing pair remains; the established exterior and possible center prove palindrome equivalence.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    private static boolean eligible(char c) {
        return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
    }
    private static char fold(char c) {
        return c >= 'A' && c <= 'Z' ? (char) (c + ('a' - 'A')) : c;
    }
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (!eligible(s.charAt(left))) { left++; continue; }
            if (!eligible(s.charAt(right))) { right--; continue; }
            if (fold(s.charAt(left)) != fold(s.charAt(right))) return false;
            left++; right--;
        }
        return true;
    }
    public static boolean baseline(String s) {
        StringBuilder filtered = new StringBuilder();
        for (int i = 0; i < s.length(); i++) if (eligible(s.charAt(i))) filtered.append(fold(s.charAt(i)));
        return filtered.toString().equals(new StringBuilder(filtered).reverse().toString());
    }
}

Read the meaningful blocks

Explicit ASCII bounds

Character.isLetterOrDigit would accept a broader alphabet and change the contract. Avoid mixing a Unicode predicate with an ASCII fold.

Skip before fold

Digits remain unchanged; only A–Z receives the fixed lowercase offset.

Guard both endpoints

left<right prevents out-of-range access on empty and all-ignored strings without special allocation.

Complexity

O(n) time: each UTF-16 position is passed at most once from one end. O(1) auxiliary space, since the original String is read only.

The filter-and-reverse baseline uses O(n) storage. Unicode code-point conversion or normalization would have its own storage and semantic contract; this implementation does neither.

Exact-state walkthroughs

Reveal normal and boundary traces

Skip punctuation and fold ASCII

Input: "A,b,a!" · Result: true

Step 1 of 6: Begin at the original UTF-16 endpoints.

Every eligible symbol outside the interval has already matched; initially that exterior is empty.

UTF-16 input positions
  • 0: "A"
  • 1: ","
  • 2: "b"
  • 3: ","
  • 4: "a"
  • 5: "!"
State after this step
VariableValue
left0
right5
See the affected Java block
 1 public final class Solution {
 2     private static boolean eligible(char c) {
 3         return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
 4     }
 5     private static char fold(char c) {
 6         return c >= 'A' && c <= 'Z' ? (char) (c + ('a' - 'A')) : c;
 7     }
 8     public static boolean isPalindrome(String s) {
 9         int left = 0, right = s.length() - 1;
10         while (left < right) {
11             if (!eligible(s.charAt(left))) { left++; continue; }
12             if (!eligible(s.charAt(right))) { right--; continue; }
13             if (fold(s.charAt(left)) != fold(s.charAt(right))) return false;
14             left++; right--;
15         }
16         return true;
17     }
18     public static boolean baseline(String s) {
19         StringBuilder filtered = new StringBuilder();
20         for (int i = 0; i < s.length(); i++) if (eligible(s.charAt(i))) filtered.append(fold(s.charAt(i)));
21         return filtered.toString().equals(new StringBuilder(filtered).reverse().toString());
22     }
23 }
24

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Begin at the original UTF-16 endpoints.

    Every eligible symbol outside the interval has already matched; initially that exterior is empty.

    left
    0
    right
    5
  2. Ignore the right non-ASCII-alphanumeric code unit.

    Ignoring a symbol preserves the filtered sequence; consuming an equal pair extends the matched exterior.

    oldLeft
    0
    oldRight
    5
    left
    0
    right
    4
  3. Consume one equal folded pair.

    Ignoring a symbol preserves the filtered sequence; consuming an equal pair extends the matched exterior.

    oldLeft
    0
    oldRight
    4
    left
    1
    right
    3
  4. Ignore the left non-ASCII-alphanumeric code unit.

    Ignoring a symbol preserves the filtered sequence; consuming an equal pair extends the matched exterior.

    oldLeft
    1
    oldRight
    3
    left
    2
    right
    3
  5. Ignore the right non-ASCII-alphanumeric code unit.

    Ignoring a symbol preserves the filtered sequence; consuming an equal pair extends the matched exterior.

    oldLeft
    2
    oldRight
    3
    left
    2
    right
    2
  6. Return the contract result.

    All required values have been finalized under the declared contract.

    result
    true

Mismatch after ignoring accented symbols

Input: "éaBé" · Result: false

Step 1 of 5: Begin at the original UTF-16 endpoints.

Every eligible symbol outside the interval has already matched; initially that exterior is empty.

UTF-16 input positions
  • 0: "é"
  • 1: "a"
  • 2: "B"
  • 3: "é"
State after this step
VariableValue
left0
right3
See the affected Java block
 1 public final class Solution {
 2     private static boolean eligible(char c) {
 3         return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
 4     }
 5     private static char fold(char c) {
 6         return c >= 'A' && c <= 'Z' ? (char) (c + ('a' - 'A')) : c;
 7     }
 8     public static boolean isPalindrome(String s) {
 9         int left = 0, right = s.length() - 1;
10         while (left < right) {
11             if (!eligible(s.charAt(left))) { left++; continue; }
12             if (!eligible(s.charAt(right))) { right--; continue; }
13             if (fold(s.charAt(left)) != fold(s.charAt(right))) return false;
14             left++; right--;
15         }
16         return true;
17     }
18     public static boolean baseline(String s) {
19         StringBuilder filtered = new StringBuilder();
20         for (int i = 0; i < s.length(); i++) if (eligible(s.charAt(i))) filtered.append(fold(s.charAt(i)));
21         return filtered.toString().equals(new StringBuilder(filtered).reverse().toString());
22     }
23 }
24

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Begin at the original UTF-16 endpoints.

    Every eligible symbol outside the interval has already matched; initially that exterior is empty.

    left
    0
    right
    3
  2. Ignore the left non-ASCII-alphanumeric code unit.

    Ignoring a symbol preserves the filtered sequence; consuming an equal pair extends the matched exterior.

    oldLeft
    0
    oldRight
    3
    left
    1
    right
    3
  3. Ignore the right non-ASCII-alphanumeric code unit.

    Ignoring a symbol preserves the filtered sequence; consuming an equal pair extends the matched exterior.

    oldLeft
    1
    oldRight
    3
    left
    1
    right
    2
  4. Reject unequal eligible endpoints.

    An inner symbol cannot repair this opposing eligible mismatch.

    left
    1
    right
    2
    leftSymbol
    "a"
    rightSymbol
    "B"
    matched
    false
  5. Return the contract result.

    All required values have been finalized under the declared contract.

    result
    false

Test the contract

  1. Input: ""
    Output: true

    No retained symbols.

  2. Input: ".,!"
    Output: true

    All ignored.

  3. Input: "0P"
    Output: false

    Digits are significant.

  4. Input: "éaÉ"
    Output: true

    Only a remains under the explicit ASCII rule.

Common mistakes and counterexamples

Ignore digits

Counterexample: "0P" would wrongly become a one-letter palindrome.

Include ASCII digits alongside letters.

Use locale-dependent folding

Counterexample: Changing locale must not change the ASCII comparison.

Fold A–Z explicitly; non-ASCII symbols are ignored by contract.

Compare before skipping punctuation

Counterexample: "a!a" should match.

Move past ineligible endpoints before comparing eligible symbols.

Follow-ups

Allow one deletion.

At the first eligible mismatch, check whether deleting either eligible endpoint makes the remaining filtered interval a palindrome. Keep skipping rules consistent; arbitrary extra deletions are not allowed.

Support Unicode text.

Specify normalization form, code-point versus grapheme comparison, and case-fold expansion. A char is a UTF-16 code unit and cannot represent every Unicode character.

Return original matched positions.

Keep the original indices of each eligible comparison. Returning all pairs needs O(n) output space even when the boolean decision uses O(1) workspace.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.