Grind 75: Conquering Palindromes

As part of my journey to refresh my data structures and algorithms knowledge I recently started the Grind 75, which is supposed to be Blind 75 2.0 (same author of Blind 75).

Just to get things back in motion I have set the schedule to 5 hours / 5 weeks for a total of 41 questions on Easy difficulty.

For this first post I had set my sights on the classic isPalindrome(): determine if a given string reads the same backward as forwards.

My first attempt was a brute-force solution that iterated over the string, adding only alphanumeric characters to a new string. This ensured we only considered letters and numbers for the palindrome check. Here’s the code:

func isPalindrome(s string) bool {
	// normalize input
	// lowercase
	s = strings.ToLower(s)

	filteredS := ""

	// remove non-alphanumeric characters
	for _, c := range s {
		if !unicode.IsLetter(c) && !unicode.IsNumber(c) {
			continue
		}

		filteredS = filteredS + string(c)
	}

	strLen := len(filteredS)

	j := strLen - 1

	for i := 0; i < strLen; i++ {
		if filteredS[i] != filteredS[j] {
			return false
		}

		j--
	}

	return true
}

While this approach yielded a correct solution, it wasn’t optimal. It created a new string to store the filtered characters, which used extra memory and introduced unnecessary string concatenations. The submission was benchmarked as:

302ms runtime

#

40.28MB of memory

#

Link to initial submission

Absolutely horrible when compared with other submissions.

Building a Better Palindrome Checker

#

Attempt #1

#

The immediate optimization that came to mind was to perform the lowercase operation after filtering out alphanumeric characters to reduce the conversion operation on unnecessary characters. It also seemed like a good idea to use unicode.ToLower() as we already had the rune:

for _, c := range s {
  if !unicode.IsLetter(c) && !unicode.IsNumber(c) {
    continue
  }

  c = unicode.ToLower(c)

  filteredS = filteredS + string(c)
}

This resulted in a worse benchmark and I believe it might be because of unicode.ToLower() not being as optimized as strings.ToLower().

406ms

#

67.64MB

#

Link to submission

Attempt #2

#

Swapping out unicode.ToLower() with strings.ToLower() after filtering improved the runtime a bit, but still worse than the brute force attempt.

for _, c := range s {
  if !unicode.IsLetter(c) && !unicode.IsNumber(c) {
    continue
  }

  filteredS = filteredS + strings.ToLower(string(c))
}

369ms

#

83.11MB

#

Link to submission

Attempt #3

#

Looking to improve my solution, I explored Go’s built-in strings.Builder type. This powerful struct allows for efficient string building and concatenation. Here’s the optimized version using strings.Builder:

func isPalindrome(s string) bool {
	// lowercase
	s = strings.ToLower(s)

	var filteredS strings.Builder

	// remove non-alphanumeric characters
	for _, c := range s {
		if !unicode.IsLetter(c) && !unicode.IsNumber(c) {
			continue
		}

    filteredS.WriteString(string(c))
	}

	// strLen := len(filteredS)

	j := filteredS.Len() - 1

	for i := 0; i < filteredS.Len(); i++ {
		if filteredS.String()[i] != filteredS.String()[j] {
			return false
		}

		j--
	}

	return true
}

5ms

#

3.47MB

#

Link to submission

Attempt #4

#

The last optimization that seemed obvious was to use string.Builder’s WriteRune() method and go back to unicode.ToLower() on filtered characters to prevent extra type conversions:

for _, c := range s {
  if !unicode.IsLetter(c) && !unicode.IsNumber(c) {
    continue
  }

  c = unicode.ToLower(c)

  filteredS.WriteRune(c)
}

0ms

#

3.32MB

#

Link to submission

That resulted in a runtime measured in the nanoseconds, somehow beating out 100% of submissions. Mission accomplished.

Key Learnings

#

This exercise highlighted the importance of considering efficiency when solving problems. While a naive solution might work, it’s often beneficial to explore alternative approaches that can improve runtime and memory usage. Go’s strings.Builder provided an elegant way to achieve this optimization.

This journey through isPalindrome() is just a small step in my quest to revamp my data structures and algorithms foundation. I’m excited to tackle more problems and keep sharing my learnings along the way!