Valid Palindrome Two Pointer in DSA Go - Execution Trace

Concept Flow - Valid Palindrome Two Pointer

Start: left=0, right=len-1

↓

Check chars at left and right

↓

Move left++ and right--

↓

left >= right?

Yes↓

Return true

Two pointers start at the string ends, move inward comparing characters. If mismatch found, return false; if pointers cross, return true.

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 is a palindrome by comparing characters from both ends moving inward.

Execution Table

Step	Operation	left	right	Chars Compared	Match?	Action	Result
1	Initialize pointers	0	6	-	-	Start comparison	Continue
2	Compare s[left] and s[right]	0	6	'r' vs 'r'	Yes	left++, right--	Continue
3	Compare s[left] and s[right]	1	5	'a' vs 'a'	Yes	left++, right--	Continue
4	Compare s[left] and s[right]	2	4	'c' vs 'c'	Yes	left++, right--	Continue
5	Compare s[left] and s[right]	3	3	'e' vs 'e'	Yes	left++, right--	Pointers crossed
6	Check pointers	4	2	-	-	left >= right	Return true

💡 Pointers crossed without mismatch, string is palindrome

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
left	0	1	2	3	4	4
right	6	5	4	3	2	2

Key Moments - 3 Insights

Why do we stop when left >= right?

Because when left pointer passes or meets right pointer, all character pairs have been checked and matched (see execution_table step 6).

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

We immediately return false as shown in execution_table step 3 if mismatch occurs, no need to check further.

Why do we increment left and decrement right only when characters match?

Because only matching pairs allow us to move inward and continue checking; mismatch means palindrome check fails early (see steps 2-5).

Visual Quiz - 3 Questions

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

A left=3, right=3

B left=2, right=4

C left=4, right=2

D left=1, right=5

💡 Hint

Check the 'left' and 'right' columns in execution_table row for step 4

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

A Step 5

B Step 6

C Step 4

D Step 3

💡 Hint

Look at the 'Result' column where it says 'Return true'

If the characters at s[left] and s[right] were different at step 3, what would happen?

A The function would continue checking next pairs

B The function would return false immediately

C The pointers would move inward anyway

D The function would return true immediately

💡 Hint

See the 'Match?' and 'Action' columns in execution_table step 3

Concept Snapshot

Two pointers start at string ends
Compare characters moving inward
If mismatch found, return false
If pointers cross, return true
Efficient palindrome check in O(n) time

Full Transcript

This concept uses two pointers starting at the beginning and end of a string. They compare characters at these positions. If the characters match, both pointers move inward by one. If they don't match, the function returns false immediately. When the pointers cross or meet, it means all characters matched and the string is a palindrome, so the function returns true. This method efficiently checks palindrome property in one pass.

Practice

1. What does the two-pointer technique check when verifying if a string is a palindrome?

easy

A. It compares characters from the start and end moving towards the center

B. It counts the number of vowels in the string

C. It reverses the string and compares with the original

D. It sorts the characters and checks if sorted equals original

Solution

1. Step 1: Understand two-pointer approach

   The two-pointer technique uses two indexes: one at the start and one at the end of the string.

2. Step 2: Compare characters moving inward

   It compares characters at these pointers and moves them towards the center to check if they match.

3. Final Answer:

   It compares characters from the start and end moving towards the center -> Option A

4. Quick Check:

   Two-pointer = compare start/end chars [OK]

Hint: Check characters from both ends moving inward [OK]

Common Mistakes:

• Thinking it counts vowels instead of comparing characters
• Assuming it reverses the string explicitly
• Confusing sorting with palindrome check

2. Which of the following Go code snippets correctly initializes two pointers for a palindrome check on string s?

easy

A. left := len(s); right := 0

B. left := 1; right := len(s)

C. left := -1; right := len(s) + 1

D. left := 0; right := len(s) - 1

Solution

1. Step 1: Identify valid pointer initialization

   For a string, the first character index is 0 and last is length minus 1.

2. Step 2: Check each option

   left := 0; right := len(s) - 1 correctly sets left to 0 and right to len(s)-1, valid for two-pointer palindrome check.

3. Final Answer:

   left := 0; right := len(s) - 1 -> Option D

4. Quick Check:

   Start=0, End=len(s)-1 [OK]

Hint: Start left at 0 and right at len(s)-1 [OK]

Common Mistakes:

• Starting left at 1 instead of 0
• Setting right to len(s) which is out of range
• Using negative or invalid indices

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

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
}

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

medium

A. true\nfalse

B. false\ntrue

C. true\ntrue

D. false\nfalse

Solution

1. Step 1: Trace "racecar" input

   Characters at start and end match moving inward, so function returns true.

2. Step 2: Trace "hello" input

   Characters 'h' and 'o' differ at first check, so function returns false.

3. Final Answer:

   true\nfalse -> Option A

4. Quick Check:

   "racecar" palindrome = true, "hello" not = false [OK]

Hint: Check first and last chars; mismatch means false [OK]

Common Mistakes:

• Assuming "hello" is palindrome
• Confusing return values order
• Ignoring early return on mismatch

4. Identify the bug in this Go function that checks palindrome:

func isPalindrome(s string) bool {
    left, right := 0, len(s)
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

medium

A. left should start at 1, not 0

B. The loop condition should be left <= right

C. right should be initialized to len(s)-1, not len(s)

D. The function should return false at the end

Solution

1. Step 1: Check pointer initialization

   right is set to len(s), which is out of string index range (0 to len(s)-1).

2. Step 2: Correct initialization

   right should be len(s)-1 to point to last character correctly.

3. Final Answer:

   right should be initialized to len(s)-1, not len(s) -> Option C

4. Quick Check:

   Index out of range error fixed by right = len(s)-1 [OK]

Hint: Set right pointer to len(s)-1 to avoid index error [OK]

Common Mistakes:

• Using len(s) as index causes runtime error
• Changing left pointer start incorrectly
• Misunderstanding loop condition

5. Given the string s = "A man, a plan, a canal: Panama", which modification to the two-pointer palindrome check is needed to correctly identify it as a palindrome?

hard

A. Reverse the string and compare directly

B. Ignore non-alphanumeric characters and compare case-insensitively

C. Only compare vowels in the string

D. Convert string to uppercase and compare characters directly

Solution

1. Step 1: Understand input complexity

   The string contains spaces, commas, and mixed cases which should be ignored for palindrome check.

2. Step 2: Modify two-pointer logic

   Skip non-alphanumeric characters and compare characters in lowercase to handle case differences.

3. Final Answer:

   Ignore non-alphanumeric characters and compare case-insensitively -> Option B

4. Quick Check:

   Clean and lowercase string before two-pointer check [OK]

Hint: Skip symbols and compare lowercase chars [OK]

Common Mistakes:

• Not ignoring spaces and punctuation
• Comparing case-sensitively causing false negatives
• Only converting case without skipping symbols