There is a string of length N made only of letters a. Whenever there are two identical adjacent letters (e.g. aa), they can be transformed into a single letter that is the next letter of the alphabet. For example, aa can be transformed into b and ee into f. However, zz cannot be further transformed.
What is the alphabetically largest string that can be obtained from the initial string?
Write a function:
def solution(N)that, given an integer N, returns the alphabetically largest string that can be obtained after such transformations.
Examples:
- Given
N = 11, the function should return'dba'. The initial string'aaaaaaaaaaa'can be transformed in the following manner:'aaaaaaaaaaa' -> 'bbbbba' -> 'ccba' -> 'dba'. - Given
N = 1, the function should return'a'. The initial string'a'cannot be transformed in any way.
The problem reduces to repeatedly merging pairs of identical letters, which is equivalent to decomposing the initial count N into powers of two. Each set bit in the binary representation of N contributes one character, with higher powers mapping to later letters, producing the lexicographically largest possible string. For example, 11 = 8 + 2 + 1 becomes 'dba'.
