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.
这道题的核心是把长度为 N 的全是 a 的字符串，反复进行“相邻两个相同字符合并成下一个字母”的操作，最终得到字典序最大的字符串。观察可知，字符串中的每一次合并本质上都等价于把字符个数按二进制拆分：每个 2^k 个相同字母可以继续向更高一位合并，因此最终结果就是把 N 分解成二进制表示后，对应生成若干按字母递增的字符。例如 N=11=8+2+1，会得到 dba。实现时只需要根据 N 的二进制位，从低位到高位依次构造结果即可，时间复杂度和结果长度都很小，适合面试中的数学 / 贪心构造题。
