Compute permutations with repeated letters
Company: Optiver
Role: Software Engineer
Category: Statistics & Math
Difficulty: easy
Interview Round: Online Assessment
Given two nonnegative integers m and n, how many distinct strings can be formed that contain exactly m copies of the character 'a' and n copies of the character 'b'? Provide the closed-form count and a short justification. Then generalize your answer to an alphabet with k distinct characters occurring with counts c1, c2, ..., ck (sum ci = N), and give the corresponding formula.
Overview: This question evaluates combinatorics and counting principles within the Statistics & Math domain, focusing on permutations with repeated characters and the generalization to multiple symbol counts.
Read the full Optiver Software Engineer interview experience this question came from
Community answers
Answer by sxm1774
For two characters ('a' appearing m times, 'b' appearing n times), the total length is m + n. There are (m+n)! permutations assuming all characters are distinct. Since the m copies of 'a' and n copies of 'b' are identical, we divide out their internal permutations to avoid overcounting:
(m+n)! / (m! n!)
For k distinct characters with counts c_1, c_2, ..., c_k summing to N:
N! / product {i=1-k} c_i! = N! / (c_1!, c_2!, .. c_k! )