Most Common Word

LeetCode 819 · View on LeetCode

Given a paragraph and a list of banned words, find the most frequent word that is not banned. Words are case-insensitive and separated by any non-letter character.

package main

import "fmt"

func mostCommonWord(paragraph string, banned []string) string {
	ban := map[string]bool{}
	for _, b := range banned {
		ban[b] = true
	}

	freq := map[string]int{}
	word := []byte{}
	for i := 0; i <= len(paragraph); i++ {
		if i < len(paragraph) && (paragraph[i] >= 'a' && paragraph[i] <= 'z' || paragraph[i] >= 'A' && paragraph[i] <= 'Z') {
			word = append(word, paragraph[i]|32) // lowercase via bit trick
		} else if len(word) > 0 {
			w := string(word)
			if !ban[w] {
				freq[w]++
			}
			word = word[:0]
		}
	}

	most, maxCount := "", 0
	for w, c := range freq {
		if c > maxCount {
			most, maxCount = w, c
		}
	}
	return most
}

func main() {
	paragraph := "Bob hit a ball, the hit BALL flew far after it was hit."
	banned := []string{"hit"}
	fmt.Println(mostCommonWord(paragraph, banned)) // "ball"
}

Key techniques:

paragraph[i]|32 lowercases ASCII letters (sets the 6th bit)
Loop to i <= len(paragraph) flushes the last word without special-casing
Map for banned words gives O(1) lookup vs slice scan