Start learning free

LESSON 228 OF 667 · LOOPS WITH STRINGS, ARRAYS & DICTIONARIES

Group Words by First Letter in C++: A Map of Vectors

Practice Read the full explanation

Given a vector words of lowercase words, group the words by their first letter. Return an unordered_map where each key is a first letter, written as a one-character string, and its value is a vector of all the words that start with that letter.

Inside each group, keep the words in the order they have in words. The order of the entries in the unordered_map doesn't matter.

Example 1:

Input: words = ["apple", "banana", "avocado", "blueberry", "cherry"]
Output: {"a": ["apple", "avocado"], "b": ["banana", "blueberry"], "c": ["cherry"]}
Explanation: "apple" and "avocado" start with "a", "banana" and "blueberry" start with "b", and "cherry" is alone under "c".

Example 2:

Input: words = ["dog", "cat", "deer", "cow", "duck"]
Output: {"d": ["dog", "deer", "duck"], "c": ["cat", "cow"]}
Explanation: "dog" comes before "deer" and "duck" in words, so it comes first in the "d" group too.

Example 3:

Input: words = ["hello"]
Output: {"h": ["hello"]}
Explanation: One word makes one group.

Rules:

  • words has at least one word.
  • Every word has at least one letter and only lowercase letters a-z.
  • A word that appears more than once in words appears as many times in its group.
STEP 1 OF 5
    Ctrl + Enter to check

    C++ · LOOPS WITH STRINGS, ARRAYS & DICTIONARIES

    Group Words By First Letter in C++, explained

    Problem overview

    The function groupByFirstLetter takes a vector<string> named words of lowercase words and returns an unordered_map<string, vector<string>>. Each key is a first letter written as a one-character string, and its value is a vector of every word that starts with that letter. Inside a group the words keep the order they have in words. The order of the groups doesn't matter.

    For ["apple", "banana", "avocado", "blueberry", "cherry"] the groups are a: [apple, avocado], b: [banana, blueberry] and c: [cherry]. A word that appears more than once in words appears that many times in its group.

    Approach: a map from keys to lists

    This is the grouping pattern. You walk through the input once, compute a key for each element, and append the element to the list stored under that key. Every word goes into exactly one group, so one pass is enough. Because the loop meets the words in their original order and appends each at the end of its group, every group keeps that order.

    The nice part is that you never need to ask whether a group exists yet. The first time a letter appears, the map creates an empty vector for it, ready to receive the word.

    Step by step

    1. Create groups. An empty unordered_map<string, vector<string>>: keys are one-letter strings, values are vectors of words.
    2. Loop over the words. A range-based for gives one string named word per turn.
    3. Take the first letter. word.substr(0, 1) is the substring that starts at position 0 and has length 1. It is a string, matching the map's key type.
    4. Add the word to its group. groups[first].push_back(word); appends it to the vector stored under that letter.
    5. Return groups.

    The solution in C++

    class Solution {
    public:
        unordered_map<string, vector<string>> groupByFirstLetter(vector<string> &words) {
            unordered_map<string, vector<string>> groups;
            for (string word : words) {
                string first = word.substr(0, 1);
                groups[first].push_back(word);
            }
            return groups;
        }
    };
    

    The C++ details worth knowing:

    • [] creates the group. When first is not yet a key, groups[first] inserts it with a default-constructed value, which for a vector is an empty vector. It returns a reference to that vector, and push_back then adds the word to it. That is why no if is needed.
    • substr(0, 1), not word[0]. word[0] is a char, but the keys are strings. A char doesn't convert to a string on its own. word.substr(0, 1) gives a one-character string directly.
    • substr on an empty string. substr(0, 1) on "" returns an empty string rather than failing, but word[0] on an empty string would read past the text. The task promises every word has a letter.
    • Nested template brackets. The >> at the end of unordered_map<string, vector<string>> is fine in C++11 and later; older compilers wanted a space between the two.
    • Group order is unspecified. The order of words inside each vector is guaranteed, but the order in which the groups come out of the map is not.

    Complexity

    Time: O(n) on average for n words, since each map access takes constant time on average and push_back takes amortized constant time (copying a word costs time proportional to its length). Space: O(n), because every word is stored once in its group.

    Edge cases and common mistakes

    • One word. ["hello"] gives one group, h: [hello].
    • Repeated words. Each occurrence is appended, so a word that appears twice appears twice in its group.
    • Using word[0] as the key. It is a char, which doesn't match the string key type and doesn't compile.
    • Order inside a group. ["dog", "cat", "deer", "cow", "duck"] puts "dog" before "deer" and "duck" in group "d", because that is the order they were met.
    • Replacing instead of appending. Assigning a one-word vector to groups[first] would keep only the last word of each group.

    Testing

    Printed with the groups sorted by key:

    • ["apple", "banana", "avocado", "blueberry", "cherry"] gives a: [apple, avocado], b: [banana, blueberry] and c: [cherry].
    Keep going with C++650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free