Valid Palindrome Two Pointer in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of palindrome check with two pointers

What is the output of the following Go code that checks if a string is a palindrome ignoring non-alphanumeric characters and case?

DSA Go

package main
import (
	"fmt"
	"unicode"
)

func isPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		if !unicode.IsLetter(rune(s[left])) && !unicode.IsDigit(rune(s[left])) {
			left++
			continue
		}
		if !unicode.IsLetter(rune(s[right])) && !unicode.IsDigit(rune(s[right])) {
			right--
			continue
		}
		if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) {
			return false
		}
		left++
		right--
	}
	return true
}

func main() {
	fmt.Println(isPalindrome("A man, a plan, a canal: Panama"))
}

A Compilation error

B true

C Runtime panic

D false

💡 Hint

Focus on how the two pointers skip non-alphanumeric characters and compare letters ignoring case.

The code uses two pointers moving inward, skipping non-alphanumeric characters, and compares characters case-insensitively. The input string is a classic palindrome phrase ignoring punctuation and spaces, so the function returns true.

❓ Predict Output

intermediate

Result of palindrome check on non-palindrome string

What does the following Go code print when checking if "race a car" is a palindrome?

DSA Go

package main
import (
	"fmt"
	"unicode"
)

func isPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		if !unicode.IsLetter(rune(s[left])) && !unicode.IsDigit(rune(s[left])) {
			left++
			continue
		}
		if !unicode.IsLetter(rune(s[right])) && !unicode.IsDigit(rune(s[right])) {
			right--
			continue
		}
		if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) {
			return false
		}
		left++
		right--
	}
	return true
}

func main() {
	fmt.Println(isPalindrome("race a car"))
}

A Compilation error

B true

C false

D Runtime panic

💡 Hint

Check the characters compared after skipping spaces.

The string "race a car" is not a palindrome when ignoring spaces and case because the characters compared at the middle differ.

🧠 Conceptual

advanced

Why use two pointers for palindrome check?

Why is the two-pointer technique efficient for checking if a string is a palindrome ignoring non-alphanumeric characters and case?

A It allows checking characters from both ends simultaneously, skipping irrelevant characters, reducing time complexity to O(n).

B It sorts the string first, then compares characters, which is faster than direct comparison.

C It uses recursion to compare characters, which is more memory efficient.

D It converts the string to uppercase first, then compares characters sequentially.

💡 Hint

Think about how two pointers move and skip characters.

Two pointers start from the beginning and end, moving inward and skipping non-alphanumeric characters. This avoids extra space and checks only necessary characters in one pass, making it O(n).

🔧 Debug

advanced

Identify the bug in palindrome check code

What error will the following Go code produce when checking if "No lemon, no melon" is a palindrome?

DSA Go

package main
import (
	"fmt"
	"unicode"
)

func isPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		if !unicode.IsLetter(rune(s[left])) {
			left++
			continue
		}
		if !unicode.IsLetter(rune(s[right])) {
			right--
			continue
		}
		if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) {
			return false
		}
		left++
		right--
	}
	return true
}

func main() {
	fmt.Println(isPalindrome("No lemon, no melon"))
}

A Index out of range runtime panic

B false

C true

D Compilation error

💡 Hint

Check what happens when the code encounters a comma or space on the right pointer.

The code only skips letters but does not skip digits or other characters. The comma and space are not letters, so the right pointer decrements correctly. However, the code does not check digits or other non-alphanumeric characters, so it may cause incorrect comparisons or index errors if input contains digits or other characters.

🚀 Application

expert

Count palindromic substrings using two pointers

Given a string, which approach correctly counts all palindromic substrings using the two-pointer technique?

A Reverse the string and count matching prefixes and suffixes.

B Sort the string and count repeated characters as palindromes.

C Use a stack to push characters and pop when matching characters are found.

D Expand around each character and each pair of characters as centers, using two pointers to check palindrome substrings.

💡 Hint

Think about how two pointers can expand outwards from centers to find palindromes.

Counting palindromic substrings can be done by expanding around each character (odd length) and each pair (even length) using two pointers moving outward while characters match.

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