Palindrome Detection in DSA Javascript - Execution Trace

Concept Flow - Palindrome Detection

Start with input string

↓

Set left pointer at start

↓

Set right pointer at end

↓

Compare characters at left and right

↓

Return False: Not palindrome

Yes↓

Move left pointer right

↓

Move right pointer left

↓

Left pointer >= Right pointer?

No→Repeat comparison

Yes↓

Return True: Is palindrome

We check characters from both ends moving inward. If all pairs match, it's a palindrome.

Execution Sample

DSA Javascript

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

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

Execution Table

Step	Operation	Left Pointer	Right Pointer	Characters Compared	Match?	Action	Result So Far
1	Initialize pointers	0	6	-	-	Start comparison	Undecided
2	Compare s[0] and s[6]	0	6	'r' vs 'r'	Yes	Move pointers inward	Undecided
3	Compare s[1] and s[5]	1	5	'a' vs 'a'	Yes	Move pointers inward	Undecided
4	Compare s[2] and s[4]	2	4	'c' vs 'c'	Yes	Move pointers inward	Undecided
5	Check pointers	3	3	-	-	Left >= Right, stop	Palindrome confirmed
6	Return result	-	-	-	-	-	True

💡 Left pointer reached or passed right pointer, all compared characters matched.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
left	0	1	2	3	3	3
right	6	5	4	3	3	3
result	Undecided	Undecided	Undecided	Undecided	Palindrome confirmed	True

Key Moments - 3 Insights

Why do we stop comparing when left pointer is equal to or greater than right pointer?

Because when left >= right, all character pairs have been checked. See execution_table row 5 where pointers meet, confirming palindrome.

What happens if characters at left and right pointers do not match?

The function immediately returns false, ending the check early. This is shown in the 'Match?' column where a 'No' would cause an immediate return.

Why do we move left pointer right and right pointer left after each successful comparison?

To check the next inner pair of characters. This is shown in execution_table rows 2-4 where pointers move inward after matching characters.

Visual Quiz - 3 Questions

Look at the execution_table, what characters are compared at step 3?

A 'a' vs 'a'

B 'c' vs 'c'

C 'r' vs 'r'

D 'e' vs 'e'

💡 Hint

Check the 'Characters Compared' column at step 3 in execution_table.

At which step does the left pointer become equal to the right pointer?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at 'Left Pointer' and 'Right Pointer' columns in execution_table rows.

If the characters at s[1] and s[5] did not match, what would happen?

A The function would continue checking other characters.

B The function would return false immediately.

C The pointers would move inward anyway.

D The function would return true immediately.

💡 Hint

Refer to the 'Match?' and 'Action' columns in execution_table for mismatch behavior.

Concept Snapshot

Palindrome Detection:
- Use two pointers: left at start, right at end
- Compare characters at pointers
- If mismatch, return false immediately
- Move pointers inward if match
- Stop when left >= right
- Return true if all pairs match

Full Transcript

Palindrome detection checks if a string reads the same forwards and backwards. We start with two pointers: one at the beginning (left) and one at the end (right) of the string. We compare the characters at these pointers. If they match, we move the left pointer one step right and the right pointer one step left, then compare again. If at any point the characters do not match, we return false immediately because the string is not a palindrome. We continue this process until the left pointer is equal to or passes the right pointer, which means all character pairs matched and the string is a palindrome, so we return true.

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