Palindrome Detection in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a palindrome?

A palindrome is a word, phrase, number, or sequence that reads the same backward as forward, ignoring spaces, punctuation, and capitalization.

beginner

How can you check if a string is a palindrome using two pointers?

Use two pointers: one starting at the beginning and one at the end of the string. Move both pointers towards the center, comparing characters. If all pairs match, the string is a palindrome.

intermediate

Why do we ignore case and non-alphanumeric characters when detecting palindromes?

Ignoring case and non-alphanumeric characters helps detect palindromes in phrases or sentences where spaces, punctuation, or letter case do not affect the palindrome property.

intermediate

What is the time complexity of checking a palindrome using the two-pointer technique?

The time complexity is O(n), where n is the length of the string, because each character is checked at most once.

beginner

Show a simple Java method signature for palindrome detection.

public static boolean isPalindrome(String s) { ... }

Which of the following strings is a palindrome?

A racecar

B hello

C world

D java

racecar reads the same backward and forward.

What technique uses two pointers to check palindrome?

A Divide and conquer

B Two-pointer technique

C Dynamic programming

D Greedy algorithm

Two-pointer technique compares characters from both ends moving towards the center.

When checking palindromes, why do we often remove spaces and punctuation?

A To simplify the string and focus on letters and digits

B To increase string length

C To make the string uppercase

D To sort the characters

Removing spaces and punctuation helps detect palindromes in phrases ignoring non-alphanumeric characters.

What is the time complexity of palindrome detection using two pointers?

A O(log n)

B O(n^2)

C O(1)

D O(n)

Each character is checked once, so time complexity is linear.

Which Java method signature correctly represents a palindrome check?

A private void checkPalindrome()

B public int palindromeCheck(String s)

C public static boolean isPalindrome(String s)

D public String palindrome(String s)

The method returns a boolean indicating if the string is a palindrome.

Explain how the two-pointer technique works for palindrome detection.

Think about checking characters from both ends moving inward.

Describe why preprocessing a string (like removing spaces and converting to lowercase) is important in palindrome detection.

Consider how phrases with spaces and punctuation can still be palindromes.

Practice

1. What does a palindrome string mean in the context of palindrome detection?

easy

A. A string with all unique characters

B. A string that contains only vowels

C. A string that is sorted alphabetically

D. A string that reads the same forwards and backwards

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same forwards and backwards.

2. Step 2: Compare options with definition

   Only "a string that reads the same forwards and backwards" matches this definition exactly.

3. Final Answer:

   A string that reads the same forwards and backwards -> Option D

4. Quick Check:

   Palindrome = Same forwards and backwards [OK]

Hint: Palindrome means mirror reading same both ways [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Thinking palindrome means sorted string
• Assuming palindrome only has vowels

2. Which of the following Java code snippets correctly checks if a string s is a palindrome?

easy

A. for (int i = 0; i < s.length() / 2; i++) { if (s.charAt(i) != s.charAt(s.length() - 1 - i)) return false; } return true;

B. for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != s.charAt(i + 1)) return false; } return true;

C. for (int i = 0; i < s.length() / 2; i++) { if (s.charAt(i) == s.charAt(i + 1)) return false; } return true;

D. for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != s.charAt(s.length() - i)) return false; } return true;

Solution

1. Step 1: Check loop and character comparison logic

   for (int i = 0; i < s.length() / 2; i++) { if (s.charAt(i) != s.charAt(s.length() - 1 - i)) return false; } return true; compares characters from start and end moving towards center correctly.

2. Step 2: Identify errors in other options

   Adjacent chars comparison is incorrect; equality check instead of inequality is wrong; off-by-one index error.

3. Final Answer:

   for (int i = 0; i < s.length() / 2; i++) { if (s.charAt(i) != s.charAt(s.length() - 1 - i)) return false; } return true; -> Option A

4. Quick Check:

   Compare chars from ends moving inward [OK]

Hint: Compare chars from start and end moving inward [OK]

Common Mistakes:

• Using wrong indices causing index out of bounds
• Comparing adjacent characters instead of mirrored ones
• Incorrect loop range causing incomplete checks

3. What will be the output of the following Java code?

String s = "racecar";
boolean isPalindrome = true;
for (int i = 0; i < s.length() / 2; i++) {
    if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome);

medium

A. false

B. Compilation error

C. true

D. Runtime exception

Solution

1. Step 1: Analyze the string and loop logic

   String "racecar" is a palindrome. Loop compares mirrored characters correctly.

2. Step 2: Check if any mismatch occurs

   No mismatch found, so isPalindrome remains true and prints true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   "racecar" reads same forwards and backwards [OK]

Hint: Check mirrored chars; no mismatch means true [OK]

Common Mistakes:

• Assuming palindrome check fails for odd length strings
• Confusing loop range causing missed checks
• Misreading output as string instead of boolean

4. Identify the error in the following Java code that attempts to check if a string str is a palindrome:

boolean checkPalindrome(String str) {
    for (int i = 0; i <= str.length() / 2; i++) {
        if (str.charAt(i) != str.charAt(str.length() - i)) {
            return false;
        }
    }
    return true;
}

medium

A. The loop condition should be i < str.length() / 2 instead of <=.

B. The index str.length() - i causes an index out of bounds error.

C. The method should return void instead of boolean.

D. The comparison operator should be == instead of !=.

Solution

1. Step 1: Check index usage in charAt

   Index str.length() - i is off by one; last valid index is str.length() - 1.

2. Step 2: Identify error cause

   Accessing str.charAt(str.length() - i) when i=0 causes index out of bounds.

3. Final Answer:

   Index str.length() - i causes out of bounds error -> Option B

4. Quick Check:

   String indices start at 0, max index = length-1 [OK]

Hint: Check if indices go beyond string length - 1 [OK]

Common Mistakes:

• Using <= in loop causing extra iteration
• Confusing comparison operators
• Wrong return type for boolean method

5. Given a list of strings ["level", "world", "deed", "java", "noon"], which Java code snippet correctly returns a new list containing only the palindromes?

hard

A. List<String> palindromes = list.stream().filter(s -> new StringBuilder(s).reverse().toString().equals(s)).collect(Collectors.toList());

B. List<String> palindromes = list.stream().filter(s -> s.charAt(0) == s.charAt(s.length() - 1)).collect(Collectors.toList());

C. List<String> palindromes = list.stream().filter(s -> s.length() % 2 == 0).collect(Collectors.toList());

D. List<String> palindromes = list.stream().filter(s -> s.equals(s.toUpperCase())).collect(Collectors.toList());

Solution

1. Step 1: Understand palindrome filtering logic

   List<String> palindromes = list.stream().filter(s -> new StringBuilder(s).reverse().toString().equals(s)).collect(Collectors.toList()); reverses string and compares to original, correctly identifying palindromes.

2. Step 2: Analyze other options

   Checking only first and last char equality; filtering even length strings; checking uppercase equality; all incorrect.

3. Final Answer:

   List<String> palindromes = list.stream().filter(s -> new StringBuilder(s).reverse().toString().equals(s)).collect(Collectors.toList()); -> Option A

4. Quick Check:

   Reverse string equals original means palindrome [OK]

Hint: Reverse string and compare to original to find palindrome [OK]

Common Mistakes:

• Checking only first and last characters
• Filtering by string length instead of palindrome
• Confusing uppercase check with palindrome