How should I practice Assign Distinct Letter Values to Minimize XOR?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Wayfair phone screen problems in FastPrep.

Is Assign Distinct Letter Values to Minimize XOR associated with Wayfair?

FastPrep tags this as a Wayfair phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Assign Distinct Letter Values to Minimize XOR

Learn this problem

● Hard

WayfairFULLTIMEPHONE SCREEN

Problem statement

You are given a non-empty lowercase string s. Assign a distinct integer in [0,100] to every distinct letter.

The mapped XOR is the bitwise XOR of the assigned value for every character occurrence in s. Minimize that XOR.

Canonical Output

List the odd-frequency letters in alphabetical order, followed by the even-frequency letters in alphabetical order. Return their assigned values in that order. Among all minimum-XOR assignments, use the lexicographically smallest increasing value sequence for the odd-frequency letters. Then assign each even-frequency letter the smallest value not already used.

Function

assignLetterValues(s: String) → int[]

Examples

Example 1

s = "abbccc"return = [0,1,2]

The odd-frequency letters are a,c, and 0 XOR 1 = 1 is the minimum possible XOR for two distinct values. Even-frequency b receives the smallest unused value, 2.

Example 2

s = "aabb"return = [0,1]

Both letters occur an even number of times, so the mapped XOR is already 0. They receive the smallest distinct values.

Constraints

1 <= s.length <= 100000
s contains only lowercase English letters.