Valid Palindrome Two Pointer in DSA Go

Mental Model

Check if a word reads the same forwards and backwards by comparing characters from both ends moving towards the center.

Analogy: Like checking if a necklace looks the same when flipped around by comparing beads from both ends one by one.

h -> e -> l -> l -> o
↑                 ↑
left             right

Dry Run Walkthrough

Input: string: "racecar"

Goal: Determine if the string reads the same forwards and backwards ignoring case and non-alphanumeric characters.

Step 1: Initialize left pointer at start (r) and right pointer at end (r)

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

Why: We start comparing characters from both ends

Step 2: Compare characters at left and right (r == r), move both pointers inward

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

Why: Matching characters mean palindrome so far

Step 3: Compare characters at left and right (a == a), move both pointers inward

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

Why: Continue checking inner characters

Step 4: Compare characters at left and right (c == c), move both pointers inward

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

Why: Still matching, keep going

Step 5: Left and right pointers meet at middle character (e), no mismatch found

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

Why: Middle character doesn't need comparison, palindrome confirmed

Result:

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

Annotated Code

DSA Go

package main

import (
	"fmt"
	"unicode"
)

func isPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		// Move left pointer if not alphanumeric
		for left < right && !unicode.IsLetter(rune(s[left])) && !unicode.IsDigit(rune(s[left])) {
			left++
		}
		// Move right pointer if not alphanumeric
		for left < right && !unicode.IsLetter(rune(s[right])) && !unicode.IsDigit(rune(s[right])) {
			right--
		}
		// Compare lowercase characters
		if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) {
			return false
		}
		left++
		right--
	}
	return true
}

func main() {
	test := "racecar"
	fmt.Printf("%s\nPalindrome: %v\n", test, isPalindrome(test))
}

for left < right {

loop until pointers meet or cross

for left < right && !unicode.IsLetter(rune(s[left])) && !unicode.IsDigit(rune(s[left])) { left++ }

skip non-alphanumeric characters from left

for left < right && !unicode.IsLetter(rune(s[right])) && !unicode.IsDigit(rune(s[right])) { right-- }

skip non-alphanumeric characters from right

if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) { return false }

compare characters ignoring case, return false if mismatch

left++; right--

move pointers inward to compare next pair

Output

racecar

Palindrome: true

Complexity Analysis

Time: O(n) because we scan the string once with two pointers moving inward

Space: O(1) because we use only fixed extra space for pointers and comparisons

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

Edge Cases

empty string

returns true since empty string reads the same forwards and backwards

DSA Go

for left < right {

string with only non-alphanumeric characters

skips all characters and returns true

DSA Go

for left < right && !unicode.IsLetter(rune(s[left])) && !unicode.IsDigit(rune(s[left])) { left++ }

string with mixed case and punctuation, e.g. "A man, a plan, a canal: Panama"

ignores case and punctuation, returns true

DSA Go

if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) { return false }

When to Use This Pattern

When you need to check if a string reads the same forwards and backwards ignoring spaces and punctuation, use the two-pointer palindrome pattern for efficient comparison.

Common Mistakes

Mistake: Not skipping non-alphanumeric characters before comparing
Fix: Add loops to move pointers past non-alphanumeric characters before comparison

Mistake: Comparing characters without ignoring case
Fix: Convert characters to lowercase before comparing

Mistake: Stopping loop too early or too late causing index errors
Fix: Use 'left < right' as loop condition to avoid crossing pointers

Summary

Checks if a string is a palindrome by comparing characters from both ends moving inward.

Use when you want to verify palindrome ignoring case and non-alphanumeric characters efficiently.

The key insight is to use two pointers moving inward and skip irrelevant characters before comparing.

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