1. Groups of Anagrams
Group strings by anagram class, explain the normalization key you use, and state how you preserve or order members within each group.
I would group the strings with a dictionary. For each string, I sort its characters and use that sorted string as the normalization key. Anagrams get the same key, so they go into the same list. I append each original string as I encounter it, which preserves member order inside each group. For n strings with average length k, the time is O(n * k log k). The auxiliary space is O(n * k).
See the Code while reading this explanation.
We are given a list of strings. We need to put strings together when they contain the same characters with the same counts. For example, "eat", "tea", and "ate" belong together. The main idea is to turn every string into a common form by sorting its characters. Strings with the same sorted form belong to the same group. A dictionary stores one list for each sorted form. We process the input from left to right and append each original string to its group, so members keep their relative input order.
- Should matching be case-sensitive?
- Does the order of the groups matter, or only the members inside each group?
- Should the relative input order of strings inside each group be preserved?
The input is an array of strings. The output is a list of lists. Each inner list contains one anagram group. In the diagram, the input is ["eat", "tea", "tan", "ate", "nat", "bat"]. One valid shown result is [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]. The diagram preserves the input encounter order of members inside each group.
For each string, sort its characters. The sorted string becomes the normalization key. For example, "eat", "tea", and "ate" all become "aet". The dictionary maps each sorted key to a list of the original strings that belong to that anagram class.
Start with an empty dictionary. Visit each string from left to right. Create its sorted key. If that key is not already in the dictionary, create a new empty list for it. Then append the original string to that list. Because we append strings in encounter order, the relative order of members inside every group is preserved.
Step 1 processes "eat". Its sorted key is "aet", so the dictionary becomes {"aet": ["eat"]}.
Step 2 processes "tea". Its key is also "aet", so the dictionary becomes {"aet": ["eat", "tea"]}.
Step 3 processes "tan". Its key is "ant", so a new group is created: {"aet": ["eat", "tea"], "ant": ["tan"]}.
Step 4 processes "ate". Its key is "aet", so it is appended to the first group: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}.
Step 5 processes "nat". Its key is "ant", so the second group becomes ["tan", "nat"].
Step 6 processes "bat". Its key is "abt", so a third group is created. The shown result is [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].
Two strings are anagrams when they contain the same characters with the same frequencies. Sorting those characters produces the same sequence for every string in the same anagram class. Therefore, all anagrams get the same dictionary key. Strings with different character multisets get different keys. Each dictionary key therefore represents one anagram class.
The code creates a Dictionary<string, IList<string>>. Each loop converts the current string to a char array, sorts it, and creates the normalization key. TryGetValue checks whether a group already exists. A new List<string> is created only when the key appears for the first time. The original string is appended to the group. Finally, the dictionary values are returned as the grouped result.
If there are n strings and the average string length is k, sorting one string costs O(k log k). Doing this for all strings costs O(n * k log k). Dictionary lookup and insertion are O(1) on average. The auxiliary space is O(n * k) for the stored normalization keys and groups. An empty input gives an empty result. One string gives one group. Duplicate strings stay together. Different lengths produce different sorted keys. The shown solution is case-sensitive.
The key insight is that each anagram class can be represented by one normalized string. The diagram uses the characters sorted in ascending order as that normalization key. For example, "eat", "tea", and "ate" all produce "aet". A dictionary stores sorted key -> list of original strings. The central invariant is: after each input string is processed, every processed string is stored in the list for its exact sorted-character key. Because strings are appended as they are encountered, their relative input order is preserved inside each group.
using System;
using System.Collections.Generic;
using System.Linq;
public static class Program
{
public static void Main()
{
// Use the exact example shown in the approved diagram.
string[] input = { "eat", "tea", "tan", "ate", "nat", "bat" };
// Group the input strings by their sorted-character normalization key.
IList<IList<string>> groups = GroupAnagrams(input);
// Print the result as a compact list of lists for the example run.
string output =
"[" +
string.Join(",",
groups.Select(
group => "[" + string.Join(",", group.Select(s => $"\"{s}\"")) + "]")) +
"]";
Console.WriteLine(output);
}
public static IList<IList<string>> GroupAnagrams(string[] strs)
{
// Each key is a sorted string. Each value stores original strings in encounter order.
var groups = new Dictionary<string, IList<string>>();
// Process the input from left to right so order inside each group is preserved.
foreach (string s in strs)
{
// Sort a copy of the current string's characters to create its normalization key.
char[] chars = s.ToCharArray();
Array.Sort(chars);
string key = new string(chars);
// Create a group only when this normalization key appears for the first time.
if (!groups.TryGetValue(key, out IList<string>? list))
{
list = new List<string>();
groups[key] = list;
}
// Append the original string, preserving relative input order inside this group.
list.Add(s);
}
// Return all completed anagram groups after the full input has been processed.
return groups.Values.ToList();
}
}Let n be the number of strings and k be the average string length. We sort the characters of every string. Sorting one string takes O(k log k), so the total time is O(n * k log k). Dictionary lookup and insertion are O(1) on average, so they do not change the sorting-based total. The auxiliary space is O(n * k) because the algorithm stores normalization keys and grouped strings. C# Dictionary<TKey, TValue> lookup and insertion are average-case O(1), not guaranteed worst-case O(1).
This pattern is useful when several original values need to be grouped by one shared canonical form. Examples include grouping equivalent words, organizing normalized identifiers, detecting duplicate records after normalization, and building indexes where many original values belong to the same normalized key.
This problem checks whether you can recognize that different strings can share one canonical representation. It tests dictionary design, string normalization, grouping logic, order preservation, and careful complexity analysis. The interviewer can also see whether you understand why sorting creates a correct key, whether duplicates are grouped correctly, whether you can write consistent C# collection types, and whether you distinguish average dictionary behavior from guaranteed worst-case behavior.
A common mistake is using the original string as the dictionary key instead of a normalized key, which does not group anagrams. Another mistake is creating a new list every time a key appears and losing earlier members. Candidates may sort or reorder the original input instead of sorting a character copy only for the key. They may also unnecessarily sort members inside each group and lose the encounter order shown in the diagram. Another common mistake is claiming O(n) time while ignoring the O(k log k) character-sorting cost for each string.
Explain the normalization key first: "I sort each string to get a canonical form, and that sorted form identifies its anagram group." Then show one concrete example such as "tea" -> "aet" before discussing the dictionary and complexity.
