"After beating the eggs, Dana read the next step:" "Add milk and eggs, then add flour and sugar."

Are you sure your code handles hyphenated words and standard punctuation?

Are you sure your code reasonably handles the same word with different capitalization?

Try these sentences:

We can do this in runtime and space.

The final hash we return should be the only data structure whose length is tied to n.

We should only iterate through our input string once.

We'll have to go through the entire input string, and we're returning a hash with every unique word. In the worst case every word is different, so our runtime and space cost will both be at least .

This challenge has several parts. Let's break them down.

1. Splitting the words from the input string
2. Populating the hash with each word
3. Handling words that are both uppercase and lowercase in the input string

How would you start the first part?

We could use the built-in split method to separate our words, but if we just split on spaces we'd have to iterate over all the words before or after splitting to clean up the punctuation. And consider em dashes or ellipses, which aren't surrounded by spaces but nonetheless separate words. Instead, we'll make our own split_words method, which will let us iterate over the input string only once.

How can we check if a character in our input string is a letter?

Two good options are to build a helper method or to use regular expressions. Either will work for this problem. We'll build our own helper method is_letter.

# character is a variable holding a string with length 1. def letter?(character) 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'.include?(character) end

Now how can we split each word? Let's assume, for now, that our helper method will return an array of words.

We'll iterate over all the characters in the input string. How can we identify when we've reached the end of a word?

Here's a simple example. It doesn't work perfectly yet—you'll need to add code to handle the end of the input string, hyphenated words, punctuation, and edge cases.

Now we've solved the first part of the challenge, splitting the words. The next part is populating our hash with unique words. What do we do with each word?

If the word is in the hash, we'll increment its count. Otherwise, we'll add it to the hash with a count of 1.

Alright, last part! How should we handle words that are uppercase and lowercase?

Consider these sentences:

Take some time to think of possible approaches. What are some other sentences you might run into. What are all your options?

When are words that should be lowercase not?
Why not?
What are the ideal cases we'd want in our hash?

Here are a few options:

1. Only make a word uppercase in our hash if it is always uppercase in the original string.
2. Make a word uppercase in our hash if it is ever uppercase in the original string.
3. Make a word uppercase in our hash if it is ever uppercase in the original string in a position that is not the first word of a sentence.
4. Use an API or other tool that identifies proper nouns.
5. Ignore case entirely and make every word lowercase.

What are the pros and cons for each one?

Pros and cons include:

1. Only make a word uppercase in our hash if it is always uppercase in the original string: this will have reasonable accuracy in very long strings where words are more likely to be included multiple times, but words that only ever occur as the first word in a sentence will always be included as uppercase.
2. Make a word uppercase in our hash if it is ever uppercase in the original string: this will ensure proper nouns are always uppercase, but any words that are ever at the start of sentences will always be uppercase too.
3. Make a word uppercase in our hash if it is ever uppercase in the original string in a position that is not the first word of a sentence: this addresses the problem with option (2), but proper nouns that are only ever at the start of sentences will be made lowercase.
4. Use an API or other tool that identifies proper nouns: this has a lot of potential to give us a high level of accuracy, but we'll give up control over decisions, we'll be relying on code we didn't write, and our practical runtime may be significantly increased.
5. Ignore case entirely and make every word lowercase: this will give us simplicity and consistency, but we'll lose all accuracy for words that should be uppercase.

Any of these could be considered reasonable. Importantly, none of them are perfect. They all have tradeoffs, and it is very difficult to write a highly accurate algorithm. Consider "cliff" and "bill" in these sentences:

You can choose whichever of the options you'd like, or another option you thought of. For this breakdown, we're going to choose option (1).

Now, how do we update our add_word_to_hash method to avoid duplicate words?

Think about the different possibilities:

1. The word is uppercase or lowercase.
2. The word is already in the hash or not.
3. A different case of the word is already in the hash or not.

Moving forward, we can either:

1. Check for words that are in the hash in both cases when we're done populating the hash. If we add "Vanilla" three times and "vanilla" eight times, we'll combine them into one "vanilla" at the end with a value 11.
2. Avoid ever having a word in our hash that's both uppercase and lowercase. As we add "Vanilla"s and "vanilla"s, we'd always only ever have one version in our hash.

We'll choose the second approach since it will save us a walk through our hash. How should we start?

If the word we're adding is already in the hash in its current case, let's increment its count. What if it's not in the hash?

There are three possibilities:

1. A lowercase version is in the hash (in which case we know our input word is uppercase, because if it is lowercase and already in the hash it would have passed our first check and we'd have just incremented its count)
2. An uppercase version is in the hash (so we know our input word is lowercase)
3. The word is not in the hash in any case

Let's start with the first possibility. What do we want to do?

Because we only include a word as uppercase if it is always uppercase, we simply increment the lowercase version's count.

What about the second possibility?

This is a little more complicated. We need to remove the uppercase version from our hash if we encounter a lowercase version. But we still need the uppercase version's count!

Finally, what if the word is not in the hash at all?

Easy—we add it and give it a count of 1.

Now we have all our pieces! We can split words, add them to a hash, and track the number of times each word occurs without having duplicate words of the same case. Can we improve our solution?

Let's look at our runtime and space cost. We iterate through every character in the input string once and then every word in our array once. That's a runtime of , which is the best we can achieve for this challenge (we have to look at the entire input string). The space we're using includes an array for each word and a hash for every unique word. Our worst case is that every word is different, so our space cost is also , which is also the best we can achieve for this challenge (we have to return a hash of words).

But we can still make some optimizations!

How can we make our space cost even smaller?

We're storing all our split words in a separate array. That at least doubles the memory we use! How can we eliminate the need for that array?

Right now, we store each word in our array as we split them. Instead, let's just immediately populate each word in our hash!

class WordCloudData attr_accessor :words_to_counts def initialize(input_string) @words_to_counts = {} self.populate_words_to_counts(input_string) end def populate_words_to_counts(input_string) # Iterates over each character in the input string, splitting # words and passing them to add_word_to_hash(). current_word_start_index = 0 current_word_length = 0 input_string.each_char.with_index do |character, index| # If we reached the end of the string we check if the last # character is a letter and add the last word to our hash. if index == input_string.length - 1 if self.letter?(character) current_word_length += 1 end if current_word_length > 0 current_word = input_string.slice(current_word_start_index, current_word_length) self.add_word_to_hash(current_word) end # If we reach a space or emdash we know we're at the end of a word, # so we add it to our hash and reset our current word. elsif character == ' ' || character == "\u2014" if current_word_length > 0 current_word = input_string.slice(current_word_start_index, current_word_length) self.add_word_to_hash(current_word) current_word_length = 0 end # We want to make sure we split on ellipses so if we get two periods in # a row we add the current word to our hash and reset our current word. elsif character == '.' if index < input_string.length - 1 && input_string[index + 1] == '.' if current_word_length > 0 current_word = input_string.slice(current_word_start_index, current_word_length) self.add_word_to_hash(current_word) current_word_length = 0 end end # If the character is a letter or an apostrophe, we add it to our current word. elsif self.letter?(character) || character == '\'' if current_word_length == 0 current_word_start_index = index end current_word_length += 1 # If the character is a hyphen, we want to check if it's surrounded by letters. # If it is, we add it to our current word. elsif character == '-' if index > 0 && self.letter?(input_string[index - 1]) && self.letter?(input_string[index + 1]) current_word_length += 1 else if current_word_length > 0 current_word = input_string.slice(current_word_start_index, current_word_length) self.add_word_to_hash(current_word) current_word_length = 0 end end end end end def add_word_to_hash(word) # If the word is already in the hash we increment its count. if @words_to_counts.include? word @words_to_counts[word] += 1 # If a lowercase version is in the hash, we know our input word must be uppercase # but we only include uppercase words if they're always uppercase, # so we just increment the lowercase version's count. elsif @words_to_counts.include? word.downcase @words_to_counts[word.downcase] += 1 # If an uppercase version is in the hash, we know our input word must be lowercase. # Since we only include uppercase words if they're always uppercase, we add the # lowercase version and give it the uppercase version's count. elsif @words_to_counts.include?(word.capitalize) @words_to_counts[word] = 1 @words_to_counts[word] += @words_to_counts[word.capitalize] @words_to_counts.delete(word.capitalize) # Otherwise, the word is not in the hash at all, lowercase or uppercase, # so we add it to the hash. else @words_to_counts[word] = 1 end end def letter?(character) 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'.include?(character) end end