A method of operating a memory device includes receiving first and second sets of bits to be stored in multi-level cells in the device. A multi-level encoding is selected from among a plurality of multi-level encodings for storing the first and second sets of bits in the multi-level cells. Each multi-level encoding includes at least four encoding levels for a respective multi-level cell. Respective multi-level encodings have respective costs associated with programming the first and second sets of bits into the multi-level cells in accordance with the respective multi-level encodings. The multi-level encoding is selected based on the respective costs of the respective encodings. The first and second sets of bits are encoded in accordance with the selected multi-level encoding to produce encoded data for storage in the device such that a respective multi-level cell stores respective bits from both the first and second sets of bits.