Codewars: Vowel Count

Return the number (count) of vowels in the given string. We will consider a, e, i, o, u as vowels for this Kata (but not y). The input string will only consist of lower case letters and/or spaces.

First Thoughts

If I’m going brute force, I’m thinking about two loops - one to loop over the characters in the string and another to loop over the vowels that are in our set above. So let’s start there.

My Solution(s)

package kata

var vowels = []rune("aeiou")

func GetCount(str string) (count int) {
  for _, c := range str {
    if isVowel(c) {
      count++
    }
  }
  
  return count
}

func isVowel(c rune) bool {
  for _, r := range vowels {
    if c == r {
      return true
    }
  }
  
  return false
}

Look at that, we’re already leveraging lessons learned from previous challenges! I know that iterating over the string in a range is going to produce runes and I can create a []rune (slice of runes) with the casting function.

Having a loop inside a loop is a common code smell and this one specifically results in a complexity of O(n^2). I know that because it’s one of the few Big O Notation matches that I’ve memorized because so many of my first attempts involve slapping loops together.

So one of the loops has to go. Since we have no way of knowing where the vowels will be, the loop over the letters in the string has to stay, but I can do better with the inner loop. I need something that can tell me if the letter I’m looking at is a vowel without going through every vowel to do it.

In Go that’s going to be a map[string]bool or map[string]int or some other map[string]something that we can easily check to get a true/false answer about the value being present.

So let’s try this again.

package kata

var vowels = map[rune]bool{
  'a': true,
  'e': true,
  'i': true,
  'o': true,
  'u': true,
}

func GetCount(str string) (count int) {
  for _, c := range str {
    _, found := vowels[c]
    if found {
      count++
    }
  }
  
  return count
}

The tests are green. Setting each one to true feels a little weird and manual but off the top of my head I’m not seeing a better way. I have the vaguest recollection about using a map[rune]interface{} because it has no size as opposd to the one bit for true/false, but beyond that I’m drawing a blank.

It does get the complexity down to O(n) though, so winning!

Let’s see what the best practice answer is…

Best Practice Solution(s)

package kata

func GetCount(str string) (count int) {
  for _, c := range str {
    switch c {
    case 'a', 'e', 'i', 'o', 'u':
      count++
    }
  }
  return count
}

I’ve never seen one where the top answer was both the best practice and the most clever solution. That’s how you know it’s cool.

I don’t think I would have considered using a switch but oddly enough I did see another developer at work do this last week. The linter complained that not all the possible cases were being considered but all they wanted to do was have something happen if specific matches were found. Now I understand why that was an interesting way to do it. Ultimately, to make the linter stop complaining, they converted it to an if statement.

If we were to do that, this is what it would look like:

package kata

func GetCount(str string) (count int) {
  for _, c := range str {
    if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' {
      count++
    }
  }
  return count
}

The developer from last week only had to account for a pair of matches, so it would have been shorter, but the switch is certainly easier to read when you start having more than a couple values to check.

The other best practice solution uses the strings package which I wanted to look at too because I’m wondering if that puts us back at the pair of loops I started with.

package kata

import "strings"

func GetCount(strn string) int {
  count := 0

  vowels := []string{"a", "e", "i", "o", "u"}

  for _, vowel := range vowels {
    count += strings.Count(strn, vowel)
  }

  return count
}

To find out, we have to go peek at that function in the strings package to see how it’s done.

// Count counts the number of non-overlapping instances of substr in s.
// If substr is an empty string, Count returns 1 + the number of Unicode
// code points in s.
func Count(s, substr string) int {
  // special case
  if len(substr) == 0 {
    return utf8.RuneCountInString(s) + 1
  }
  if len(substr) == 1 {
    return bytealg.CountString(s, substr[0])
  }
  n := 0
  for {
    i := Index(s, substr)
    if i == -1 {
      return n
    }
    n++
    s = s[i+len(substr):]
  }
}

Sure enough, after handling a couple special cases, there’s our loop. That puts this back at O(n^2) which is a worse solution than my slice of runes or the switch statement above.

Clever Solution(s)

Same as the best practice solution!

Credit to jayeshcp at Codewars for the kata.