Character Composition Classifier — Problem Statement & Solution Guide
Problem Description
Character Composition Classifier
You are given a list of strings. Your task is to partition the list into groups such that every string in a group contains exactly the same multiset of characters, regardless of the order in which those characters appear. In other words, two strings belong to the same group if one can be rearranged to form the other.
The output should be a list of groups, where each group is a list of the original strings that share the same character composition. The order of the groups and the order of strings within each group are not important.
Input Format:
- A single integer n, the number of strings.
- n lines follow, each containing one string consisting of lowercase English letters.
Output Format:
- First, output an integer g, the number of groups.
- Then output g lines. Each line starts with an integer k, the size of the group, followed by k space‑separated strings belonging to that group.
The solution must run efficiently for large inputs.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Character Composition Classifier"
WHY DOES IT MATTER?
Grouping by character composition is a fundamental pattern for detecting equivalence classes in strings, which appears in plagiarism detection, DNA sequence analysis, and caching of query results where order is irrelevant.
OPTIMIZATION CHALLENGE
The key insight is to replace pairwise comparisons with a constant‑time bucket lookup by converting each string into a deterministic, order‑independent signature, turning a quadratic problem into linear time.
REAL-WORLD CONNECTION
Think of a distributed hash table that stores files based on their content fingerprint; two files with identical content (regardless of internal ordering) map to the same bucket, just as anagrams map to the same group via a canonical fingerprint.
When coding under pressure, first write a helper that returns the canonical key (sorted string or frequency tuple) and then use a defaultdict(list) to collect groups—this isolates the tricky part and keeps the main loop clean.
COMPLEXITY AT A GLANCE
O(N * L)O(N * L)Core Theory — Why This Approach?
The problem is a classic "group anagrams" task, which can be modeled as partitioning strings by the multiset of characters they contain. A naive solution would compare each pair of strings, counting character frequencies or sorting them on the fly, leading to O(N^2 * L) time where N is the number of strings and L is the average length—untenable for large inputs. The optimal paradigm leverages a hash map where each string is transformed into a canonical representation (either a sorted version or a fixed‑size frequency vector) that uniquely identifies its character multiset; this enables O(N * L) processing by inserting each string into the bucket keyed by its canonical form.
When the alphabet is limited (e.g., lowercase English letters), a 26‑element integer array can serve as the frequency vector, which can be serialized into a string key in O(1) per character, avoiding the O(L log L) cost of sorting. For Unicode or larger alphabets, sorting each string remains practical because the dominant factor becomes the total number of characters processed. The hash map aggregates indices or original strings into groups, and the final output is simply the collection of map values. This approach scales linearly with input size and fits comfortably within typical memory constraints.
Interview Questions on This Problem
Q1How would you modify the solution to handle Unicode strings where the character set size is not bounded by 26?
Use the sorted‑string approach as the canonical key because sorting works for any character set; alternatively, build a frequency map using a hash map per string, then serialize the map (e.g., "a:2,b:1") as the key. Both methods run in O(L log L) for sorting or O(L) for hashmap counting, preserving overall O(N * L log L) or O(N * L) time respectively.
Q2What is the time and space complexity if you store the groups as lists of original indices instead of the strings themselves?
Time remains O(N * L) for building the keys; space drops to O(N) for the indices plus O(K) for the hash map where K is the number of distinct groups, because we no longer duplicate the string data.
Q3Explain why using a mutable list as a dictionary key in Python would cause a bug in this problem, and how to fix it.
Mutable lists are unhashable, so they cannot be used as dictionary keys; attempting to do so raises a TypeError. Convert the frequency list to an immutable tuple (or a string) before using it as the key.
Examples
Input
7 abc bca cab xyz zyx yxz foo
Output
3 3 abc bca cab 3 xyz zyx yxz 1 foo
Explanation: The strings are grouped by their sorted character sequence. 'abc', 'bca', and 'cab' all sort to 'abc', forming the first group. 'xyz', 'zyx', and 'yxz' all sort to 'xyz', forming the second group. 'foo' has no other match, so it forms a group of its own.
Input
6 a b c a b c
Output
3 2 a a 2 b b 2 c c
Explanation: Each letter appears twice. Sorting each string yields itself, so the groups are formed by identical letters: two 'a's, two 'b's, and two 'c's.
Input
5 abcd dcba abcd bcda abcd
Output
1 5 abcd dcba abcd bcda abcd
Explanation: All five strings contain the same multiset of characters {'a','b','c','d'}. Sorting any of them gives 'abcd', so they all belong to a single group.
Constraints
- 1 <= n <= 100000
- 1 <= length of each string <= 100
- All strings consist only of lowercase English letters
Optimal Approach & Strategy
Compute a canonical key for each string (sorted characters or a frequency vector) and insert the string into a hash map bucket keyed by that signature. After processing all strings, the map values are the required groups, achieving O(N * L) time.
Brute Force Approach
Compare every pair of strings, checking if one is a permutation of the other by sorting or counting characters; place strings into groups based on these pairwise checks. This results in O(N^2 * L) time, which quickly becomes infeasible.
Verified Code Solutions
function groupStrings(strs) {
let map = new Map();
strs.sort((a, b) => a.length - b.length);
for (let str of strs) {
let key = '';
for (let i = 0; i < str.length; i++) {
let charCode = str.charCodeAt(i) - 'a'.charCodeAt(0);
key += charCode + ',' + i;
}
if (!map.has(key)) {
map.set(key, []);
}
map.get(key).push(str);
}
return Array.from(map.values());
}class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strs) {
map<string, vector<string>> map;
sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
return a.length() < b.length();
});
for (string str : strs) {
string key;
for (int i = 0; i < str.length(); i++) {
int charCode = str[i] - 'a';
key += to_string(charCode) + ',' + to_string(i);
}
if (map.find(key) == map.end()) {
map[key] = {};
}
map[key].push_back(str);
}
return vector<vector<string>>(map.begin(), map.end());
}
}class Solution {
public List<List<String>> groupStrings(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
Arrays.sort(strs, (a, b) -> a.length - b.length);
for (String str : strs) {
StringBuilder key = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
int charCode = str.charAt(i) - 'a';
key.append(charCode).append(',').append(i);
}
if (!map.containsKey(key.toString())) {
map.put(key.toString(), new ArrayList<>());
}
map.get(key.toString()).add(str);
}
return new ArrayList<>(map.values());
}
}def groupStrings(strs):
map = {}
strs.sort(key=len)
for str in strs:
key = ''
for i in range(len(str)):
charCode = ord(str[i]) - ord('a')
key += str(charCode) + ',' + str(i)
if key not in map:
map[key] = []
map[key].append(str)
return list(map.values())function groupStrings(strs) {
let map = new Map();
strs.sort((a, b) => a.length - b.length);
for (let str of strs) {
let key = '';
for (let i = 0; i < str.length; i++) {
let charCode = str.charCodeAt(i) - 'a'.charCodeAt(0);
key += charCode + ',' + i;
}
if (!map.has(key)) {
map.set(key, []);
}
map.get(key).push(str);
}
return Array.from(map.values());
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.