Palindrome Detection in DSA Javascript

Mental Model

Check if a sequence reads the same forwards and backwards by comparing matching elements from start and end.

Analogy: Like checking if a word or phrase looks the same in a mirror placed at its center.

start -> [h] -> [e] -> [l] -> [l] -> [o] -> end
indexes: 0     1     2     3     4

Dry Run Walkthrough

Input: string: 'racecar'

Goal: Determine if 'racecar' reads the same forwards and backwards

Step 1: Compare first and last characters 'r' and 'r'

r -> a -> c -> e -> c -> a -> r
↑start         ↑end

Why: Check if characters at both ends match to confirm palindrome property

Step 2: Move inward and compare 'a' and 'a'

r -> a -> c -> e -> c -> a -> r
  ↑start     ↑end

Why: Continue checking matching pairs moving towards the center

Step 3: Move inward and compare 'c' and 'c'

r -> a -> c -> e -> c -> a -> r
    ↑start ↑end

Why: Still matching pairs, continue

Step 4: Reached middle character 'e', no mismatch found

r -> a -> c -> e -> c -> a -> r
      ↑middle

Why: Middle character does not need a pair, palindrome confirmed

Result:

r -> a -> c -> e -> c -> a -> r
Palindrome: true

Annotated Code

DSA Javascript

class PalindromeDetector {
  static isPalindrome(str) {
    let start = 0;
    let end = str.length - 1;
    while (start < end) {
      if (str[start] !== str[end]) {
        return false; // mismatch found, not palindrome
      }
      start++; // move start pointer inward
      end--;   // move end pointer inward
    }
    return true; // all pairs matched
  }
}

// Driver code
const input = 'racecar';
const result = PalindromeDetector.isPalindrome(input);
console.log(input.split('').join(' -> '));
console.log('Palindrome:', result);

if (str[start] !== str[end]) {

check if characters at start and end differ to detect mismatch

start++;

advance start pointer inward to next character

end--;

move end pointer inward to previous character

return true;

all pairs matched, confirm palindrome

Output

r -> a -> c -> e -> c -> a -> r

Palindrome: true

Complexity Analysis

Time: O(n) because we compare pairs from start and end moving inward once

Space: O(1) because only two pointers are used regardless of input size

vs Alternative: Compared to reversing the string and comparing, this method uses less space and stops early on mismatch

Edge Cases

empty string

returns true since empty string reads same forwards and backwards

DSA Javascript

while (start < end) {

single character string

returns true because single character is palindrome by definition

DSA Javascript

while (start < end) {

string with mismatch early

returns false immediately when first mismatch found

DSA Javascript

if (str[start] !== str[end]) {

When to Use This Pattern

When you need to check if a sequence reads the same forwards and backwards, use two pointers moving inward from both ends to compare characters.

Common Mistakes

Mistake: Comparing characters without moving pointers inward, causing infinite loop
Fix: Increment start and decrement end pointers inside the loop

Mistake: Not checking for mismatch and always returning true
Fix: Return false immediately when a mismatch is found

Summary

Checks if a string reads the same forwards and backwards by comparing characters from both ends.

Use when you want to verify if a word or phrase is a palindrome.

The key insight is to use two pointers moving inward to compare matching pairs efficiently.

Practice

1. What does a palindrome string mean in simple terms?

easy

A. A string that contains only vowels

B. A string that reads the same forwards and backwards

C. A string with all unique characters

D. A string that ends with a special character

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same forwards and backwards, like 'madam' or 'racecar'.

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 B

4. Quick Check:

   Palindrome = same forwards and backwards [OK]

Hint: Palindrome means same forwards and backwards [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Thinking palindrome means only vowels
• Assuming palindrome ends with special character

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

easy

A. return str === str.split('').reverse().join('');

B. return str === str.toUpperCase();

C. return str.length === 0;

D. return str.indexOf('a') !== -1;

Solution

1. Step 1: Understand palindrome check logic

   To check palindrome, reverse the string and compare with original.

2. Step 2: Analyze code snippets

   return str === str.split('').reverse().join(''); reverses the string and compares it correctly. Others do unrelated checks.

3. Final Answer:

   return str === str.split('').reverse().join(''); -> Option A

4. Quick Check:

   Reverse and compare = return str === str.split('').reverse().join(''); [OK]

Hint: Reverse string and compare to original [OK]

Common Mistakes:

• Using toUpperCase instead of reversing
• Checking string length instead of content
• Searching for a character instead of palindrome

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

function isPalindrome(s) {
  s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  return s === s.split('').reverse().join('');
}
console.log(isPalindrome('A man, a plan, a canal: Panama'));

medium

A. false

B. undefined

C. SyntaxError

D. true

Solution

1. Step 1: Normalize string by removing non-alphanumeric and lowercasing

   The string becomes 'amanaplanacanalpanama' after cleaning.

2. Step 2: Check if cleaned string equals its reverse

   Reversing 'amanaplanacanalpanama' gives the same string, so returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Clean and compare reversed string = true [OK]

Hint: Ignore case and non-letters, then compare reversed [OK]

Common Mistakes:

• Not removing spaces and punctuation
• Ignoring case differences
• Expecting false due to original formatting

4. Find the error in this palindrome check function:

function checkPalindrome(str) {
  for(let i = 0; i < str.length; i++) {
    if(str[i] !== str[str.length - i]) {
      return false;
    }
  }
  return true;
}

medium

A. Index for comparison should be str.length - i - 1

B. No error, function works correctly

C. Function should convert string to lowercase first

D. Loop should run only till half the string length

Solution

1. Step 1: Analyze index used for comparison

   Index str.length - i is off by one because string indices start at 0.

2. Step 2: Correct index calculation

   It should be str.length - i - 1 to compare correct characters from end.

3. Final Answer:

   Index for comparison should be str.length - i - 1 -> Option A

4. Quick Check:

   Off-by-one index error fixed by subtracting 1 [OK]

Hint: Remember last index is length - 1 [OK]

Common Mistakes:

• Using full length instead of half for loop
• Ignoring off-by-one in index
• Assuming case sensitivity causes error here

5. You want to check if a sentence is a palindrome ignoring spaces, punctuation, and case. Which approach is best to implement in JavaScript?

hard

A. Check if string length is even or odd first

B. Compare original string with reversed string directly

C. Remove non-alphanumeric characters, convert to lowercase, then compare with reversed string

D. Count vowels and consonants and compare counts

Solution

1. Step 1: Understand requirements for ignoring spaces, punctuation, and case

   We must clean the string by removing unwanted characters and normalize case.

2. Step 2: Choose approach that cleans and compares reversed string

   Remove non-alphanumeric characters, convert to lowercase, then compare with reversed string correctly removes non-alphanumeric characters, converts to lowercase, then compares reversed string.

3. Final Answer:

   Remove non-alphanumeric characters, convert to lowercase, then compare with reversed string -> Option C

4. Quick Check:

   Clean and compare reversed string for sentence palindrome [OK]

Hint: Clean string before palindrome check for sentences [OK]

Common Mistakes:

• Comparing raw strings with punctuation
• Ignoring case differences
• Using vowel/consonant counts which is unrelated