Group the product codes by letters

Scenario

An online store has product codes made of lowercase letters. A supplier sometimes prints the same code with its letters shuffled, so tea and eat mean the same product.

You want to group the codes that use exactly the same letters, the same number of times each. The catalogue team then reviews each group as one product.

Your task

Write group_codes(codes).

codes[i] is the i-th product code.
Two codes are in the same group when one can be made by rearranging the letters of the other.
Return the groups as lists of positions. Order the groups by the smallest position in each group, and list the positions in each group in increasing order.

Examples

Example 1 (traced)#

text2 lines

Input:  codes = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [[0, 1, 3], [2, 4], [5]]

The trace gives each code a key: its letters in sorted order. Codes with the same key share a group.

i	code	Key (sorted letters)	Groups after
0	eat	aet	aet: [0]
1	tea	aet	aet: [0, 1]
2	tan	ant	aet: [0, 1], ant: [2]
3	ate	aet	aet: [0, 1, 3], ant: [2]
4	nat	ant	aet: [0, 1, 3], ant: [2, 4]
5	bat	abt	aet: [0, 1, 3], ant: [2, 4], abt: [5]

The groups, in order of their first position, are [[0, 1, 3], [2, 4], [5]].

Example 2#

text2 lines

Input:  codes = ["a"]
Output: [[0]]

One code makes one group.

Example 3#

text2 lines

Input:  codes = ["ab", "ba", "ab"]
Output: [[0, 1, 2]]

The codes ab, ba and ab all have one a and one b, so they share one group.

Constraints

0 ≤ codes.length ≤ 100,000 (product codes)
1 ≤ codes[i].length ≤ 20
Codes use lowercase letters a to z.

What does n ≤ 10^5 tell you?

Comparing every pair of codes costs about n × n / 2 comparisons, which is 5 × 10^9 at n = 100,000. Computing one key per code costs L log L with L at most 20, so the whole job costs about n × 100 steps, or 10^7. Each code is processed once, and the map joins equal keys.

Scenario

An online store has product codes made of lowercase letters. A supplier sometimes prints the same code with its letters shuffled, so tea and eat mean the same product.

You want to group the codes that use exactly the same letters, the same number of times each. The catalogue team then reviews each group as one product.

Your task

Write group_codes(codes).

codes[i] is the i-th product code.
Two codes are in the same group when one can be made by rearranging the letters of the other.
Return the groups as lists of positions. Order the groups by the smallest position in each group, and list the positions in each group in increasing order.

Examples

Example 1 (traced)#

text2 lines

Input:  codes = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [[0, 1, 3], [2, 4], [5]]

The trace gives each code a key: its letters in sorted order. Codes with the same key share a group.

i	code	Key (sorted letters)	Groups after
0	eat	aet	aet: [0]
1	tea	aet	aet: [0, 1]
2	tan	ant	aet: [0, 1], ant: [2]
3	ate	aet	aet: [0, 1, 3], ant: [2]
4	nat	ant	aet: [0, 1, 3], ant: [2, 4]
5	bat	abt	aet: [0, 1, 3], ant: [2, 4], abt: [5]

The groups, in order of their first position, are [[0, 1, 3], [2, 4], [5]].

Example 2#

text2 lines

Input:  codes = ["a"]
Output: [[0]]

One code makes one group.

Example 3#

text2 lines

Input:  codes = ["ab", "ba", "ab"]
Output: [[0, 1, 2]]

The codes ab, ba and ab all have one a and one b, so they share one group.

Constraints

0 ≤ codes.length ≤ 100,000 (product codes)
1 ≤ codes[i].length ≤ 20
Codes use lowercase letters a to z.

What does n ≤ 10^5 tell you?