Palindrome Detection in DSA Go - 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

↓

Move left +1

↓

left < right?

↓

Repeat compare

↓

Mismatch -> Not palindrome

Two pointers start at the ends of the string and move inward, comparing characters until they meet or mismatch.

Execution Sample

DSA Go

func isPalindrome(s string) bool {
  left, right := 0, len(s)-1
  for 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	String State
1	Initialize pointers	0	4	-	-	Start comparison	"radar"
2	Compare s[left] and s[right]	0	4	"r" vs "r"	Yes	left++, right--	"radar"
3	Compare s[left] and s[right]	1	3	"a" vs "a"	Yes	left++, right--	"radar"
4	Compare s[left] and s[right]	2	2	"d" vs "d"	Yes	left >= right, stop	"radar"
5	Result	-	-	-	-	All matched, palindrome	"radar"

💡 Pointers crossed or met with all characters matched, confirming palindrome.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
left	0	1	2	2	2
right	4	3	2	2	2

Key Moments - 3 Insights

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

Because when left meets or passes right, all pairs have been checked. See execution_table step 4 where left and right both point to index 2, meaning the middle character is reached and no mismatches found.

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

The function immediately returns false, indicating the string is not a palindrome. This is shown in the execution_table where if 'Match?' was No, the action would be to return false and stop.

Why do we increment left and decrement right pointers after a successful match?

To move inward and compare the next pair of characters. This is shown in execution_table steps 2 and 3 where after matching characters, left moves right and right moves left.

Visual Quiz - 3 Questions

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

A "a" vs "a"

B "r" vs "r"

C "d" vs "d"

D "a" vs "d"

💡 Hint

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

At which step do the left and right pointers meet or cross?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Left Pointer' and 'Right Pointer' columns to see when they become equal or cross.

If the string was "hello", what would happen at the first comparison step?

A Characters match, continue

B Characters do not match, return false

C Pointers cross, return true

D Function crashes

💡 Hint

Recall that if characters at left and right pointers differ, the function returns false immediately.

Concept Snapshot

Palindrome Detection:
- Use two pointers: left at start, right at end
- Compare characters at left and right
- If mismatch, return false
- If pointers meet or cross with all matches, return true
- Moves inward by left++ and right-- each step

Full Transcript

This visualization shows how palindrome detection works by using two pointers starting at the ends of the string. Each step compares the characters at these pointers. If they match, the pointers move inward. If they don't, the function returns false immediately. When the pointers meet or cross, it means all characters matched and the string is a palindrome. The example uses the string "radar" and shows step-by-step pointer positions and comparisons.

Practice

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

easy

A. A string with all unique characters

B. A string that contains only vowels

C. A string that reads the same forwards and backwards

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 from left to right and right to left.

2. Step 2: Match options with definition

   A string that reads the same forwards and backwards matches this definition exactly, others describe different string properties.

3. Final Answer:

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

4. Quick Check:

   Palindrome = Same forwards and backwards [OK]

Hint: Check if string equals its reverse [OK]

Common Mistakes:

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

2. Which Go code snippet correctly checks if a string s is a palindrome?

easy

A. for i := 0; i < len(s)/2; i++ { if s[i] != s[len(s)-1-i] { return false } } return true

B. for i := 0; i < len(s); i++ { if s[i] == s[i+1] { return true } } return false

C. for i := 0; i < len(s)/2; i++ { if s[i] == s[len(s)-1-i] { return false } } return true

D. for i := 0; i < len(s); i++ { if s[i] != s[i] { return false } } return true

Solution

1. Step 1: Analyze palindrome check logic

   We compare characters from start and end moving towards center. If any pair differs, return false.

2. Step 2: Match code with logic

   for i := 0; i < len(s)/2; i++ { if s[i] != s[len(s)-1-i] { return false } } return true correctly compares s[i] with s[len(s)-1-i] for half the string length and returns false if mismatch found.

3. Final Answer:

   for i := 0; i < len(s)/2; i++ { if s[i] != s[len(s)-1-i] { return false } } return true -> Option A

4. Quick Check:

   Compare pairs from ends = for i := 0; i < len(s)/2; i++ { if s[i] != s[len(s)-1-i] { return false } } return true [OK]

Hint: Compare characters from ends to middle [OK]

Common Mistakes:

• Checking only adjacent characters
• Returning false when characters match
• Comparing character with itself incorrectly

3. What is the output of this Go code snippet?

func isPalindrome(s string) bool {
    for i := 0; i < len(s)/2; i++ {
        if s[i] != s[len(s)-1-i] {
            return false
        }
    }
    return true
}

fmt.Println(isPalindrome("level"))
fmt.Println(isPalindrome("hello"))

medium

A. false false

B. false true

C. true true

D. true false

Solution

1. Step 1: Check "level" palindrome

   "level" reads same forwards and backwards, so function returns true.

2. Step 2: Check "hello" palindrome

   "hello" reversed is "olleh", different, so function returns false.

3. Final Answer:

   true false -> Option D

4. Quick Check:

   "level"=true, "hello"=false [OK]

Hint: Test string and its reverse equality [OK]

Common Mistakes:

• Assuming all strings are palindrome
• Mixing output order
• Ignoring case sensitivity

4. Find the error in this Go function that checks palindrome:

func isPalindrome(s string) bool {
    for i := 0; i <= len(s)/2; i++ {
        if s[i] != s[len(s)-1-i] {
            return false
        }
    }
    return true
}

medium

A. The loop condition should be 'i < len(s)/2' to avoid index out of range

B. The comparison should be 's[i] == s[len(s)-1-i]' to return true early

C. The function should return false at the end instead of true

D. The loop should start from 'i := 1' instead of 0

Solution

1. Step 1: Analyze loop boundary

   The loop uses 'i <= len(s)/2', which causes 'i' to reach len(s)/2 inclusive, possibly exceeding index for odd length strings.

2. Step 2: Correct loop condition

   Changing to 'i < len(s)/2' ensures no index out of range error and proper comparison only up to middle.

3. Final Answer:

   The loop condition should be 'i < len(s)/2' to avoid index out of range -> Option A

4. Quick Check:

   Loop boundary off by one causes error [OK]

Hint: Use '<' not '<=' for half-length loops [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Returning wrong boolean at end
• Starting loop from 1 instead of 0

5. You want to detect if a string is a palindrome ignoring case and spaces. Which approach is best in Go?

hard

A. Check palindrome directly without changes

B. Remove spaces, convert to lowercase, then check palindrome normally

C. Only convert to lowercase, ignore spaces

D. Reverse string and compare without any changes

Solution

1. Step 1: Understand problem requirements

   We must ignore spaces and case differences when checking palindrome.

2. Step 2: Prepare string correctly

   Removing spaces and converting all letters to lowercase normalizes the string for accurate palindrome check.

3. Step 3: Check palindrome

   After normalization, use standard palindrome check comparing characters from ends.

4. Final Answer:

   Remove spaces, convert to lowercase, then check palindrome normally -> Option B

5. Quick Check:

   Normalize string before check = Remove spaces, convert to lowercase, then check palindrome normally [OK]

Hint: Clean string first: lowercase + remove spaces [OK]

Common Mistakes:

• Ignoring spaces in palindrome check
• Not converting to lowercase
• Comparing raw strings directly