Palindrome Detection in DSA Typescript - Execution Trace

Concept Flow - Palindrome Detection

Start

↓

Set pointers: left=0, right=length-1

↓

Compare characters at left and right

↓

Return False

Yes↓

Move left++ and right--

↓

Check if left >= right

↓

Return True

↩Back to Compare characters

Check characters from both ends moving inward; if all pairs match, it's a palindrome.

Execution Sample

DSA Typescript

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

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

Execution Table

Step	Operation	left index	right index	Characters Compared	Match?	Action	Result
1	Initialize pointers	0	6	-	-	Start comparison	-
2	Compare s[0] and s[6]	0	6	'r' vs 'r'	Yes	left++, right--	-
3	Compare s[1] and s[5]	1	5	'a' vs 'a'	Yes	left++, right--	-
4	Compare s[2] and s[4]	2	4	'c' vs 'c'	Yes	left++, right--	-
5	Check left >= right	3	3	-	-	left >= right true	Return True
6	End	-	-	-	-	-	Palindrome confirmed

💡 Pointers crossed or met (left >= right), 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	undefined	undefined	undefined	undefined	true	true

Key Moments - 3 Insights

Why do we stop comparing when left >= right?

Because when left meets or passes right, all character pairs have been checked (see execution_table step 5). No need to continue.

What if characters at left and right don't match?

We return false immediately (not shown in this example but in step 2-4, if 'Match?' was No, action would be 'Return False'). This stops the check early.

Why do we increment left and decrement right after each match?

To move inward and compare the next pair of characters (execution_table steps 2-4 show this pointer movement).

Visual Quiz - 3 Questions

Look at the execution_table, what are the values of left and right after step 3?

A left=2, right=4

B left=3, right=3

C left=1, right=5

D left=0, right=6

💡 Hint

Check the 'left index' and 'right index' columns in execution_table row for step 3.

At which step does the function decide the string is a palindrome?

A Step 4

B Step 5

C Step 2

D Step 6

💡 Hint

Look for the step where 'left >= right' is true and the action is 'Return True' in execution_table.

If the characters at s[2] and s[4] 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 steps 2-4 for mismatch behavior.

Concept Snapshot

Palindrome Detection:
- Use two pointers: left at start, right at end
- Compare characters at left and right
- If mismatch, return false
- Move pointers inward (left++, right--)
- Stop when left >= right, return true
- Checks if string reads same forwards and backwards

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). We compare the characters at these pointers. If they match, we move the pointers inward and continue. If they don't match, we return false immediately. When the pointers meet or cross, it means all pairs matched, so we return true. This method efficiently checks palindrome property by comparing pairs from outside to inside.

Practice

1. What does it mean if a string is a palindrome?

easy

A. The string has no spaces

B. The string reads the same forwards and backwards

C. The string contains only letters

D. The string is all uppercase

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 The string reads the same forwards and backwards matches this definition exactly.

3. Final Answer:

   The string 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 uppercase or letter-only strings
• Thinking palindrome means no spaces
• Assuming palindrome means all lowercase

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

easy

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

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

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

D. return str === str.split('').reverse();

Solution

1. Step 1: Understand string reversal in TypeScript

   To reverse a string, split it into characters, reverse the array, then join back.

2. Step 2: Check each option's correctness

   return str === str.split('').reverse().join(''); uses split(''), reverse(), join('') correctly. Others miss correct methods or arguments.

3. Final Answer:

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

4. Quick Check:

   Correct string reversal syntax = return str === str.split('').reverse().join(''); [OK]

Hint: Use split(''), reverse(), join('') to reverse strings [OK]

Common Mistakes:

• Using reverse() directly on string (not an array)
• Using split() without arguments returns whole string as one element
• Forgetting to join array back to string

3. What will be the output of this TypeScript code?

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

medium

A. true

B. false

C. SyntaxError

D. undefined

Solution

1. Step 1: Clean the string

   The string is converted to lowercase and non-alphanumeric characters removed, resulting in 'amanaplanacanalpanama'.

2. Step 2: Check palindrome condition

   This cleaned string equals its reverse, so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cleaned string equals reversed = true [OK]

Hint: Clean string before checking palindrome for accurate result [OK]

Common Mistakes:

• Not cleaning string before palindrome check
• Assuming spaces or punctuation affect palindrome
• Confusing true/false output

4. Find the error in this palindrome check function:

function checkPalindrome(str: string): boolean {
  const reversed = str.split('').reverse();
  return str === reversed;
}

medium

A. reverse() does not work on strings

B. Function missing return type

C. split('') is incorrect usage

D. reversed is an array, not a string

Solution

1. Step 1: Analyze reversed variable type

   reversed is an array after split and reverse, not a string.

2. Step 2: Compare string with array

   Comparing string to array returns false always; need to join array back to string.

3. Final Answer:

   reversed is an array, not a string -> Option D

4. Quick Check:

   Compare string to string, not array [OK]

Hint: Join reversed array back to string before comparing [OK]

Common Mistakes:

• Comparing string directly to array
• Forgetting to join reversed array
• Assuming split('') returns string

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

hard

A. Convert to lowercase, remove non-alphanumeric chars, then compare with reversed

B. Compare original string with reversed string directly

C. Remove spaces only, then compare

D. Convert to uppercase and compare with reversed uppercase

Solution

1. Step 1: Understand palindrome ignoring spaces and punctuation

   We must clean the string by removing spaces and punctuation and normalize case.

2. Step 2: Choose correct cleaning and comparison

   Convert to lowercase, remove non-alphanumeric chars, then compare with reversed cleans string by removing non-alphanumeric characters and lowercases it before comparing with reversed.

3. Final Answer:

   Convert to lowercase, remove non-alphanumeric chars, then compare with reversed -> Option A

4. Quick Check:

   Clean and normalize before palindrome check [OK]

Hint: Clean string fully before palindrome check for accuracy [OK]

Common Mistakes:

• Only removing spaces but not punctuation
• Comparing without case normalization
• Assuming uppercase conversion alone is enough