题解 | #String II#

记录数组中转变为其他字符的代价,遍历所有转变后的字符,对于每个字符,我们贪心地修改代价最小的,最后返回可以获得的最大个数即可

import heapq
class Solution:
    def string2(self , k , s ):
        v = {}
        for i in range(len(s)):
            v[i] = [float('inf')] * 26
            for j in range(97,123):
                if j >= ord(s[i]):
                    v[i][j - 97] = j - ord(s[i])
                else:
                    v[i][j - 97] = ord(s[i]) - j

        def trans(c):
            heap = []
            for i in range(len(s)):
                heapq.heappush(heap,v[i][ord(c) - 97])
            ans = 0
            cnt = k
            while cnt > 0 and heap:
                cur_v = heapq.heappop(heap)
                cnt -= cur_v
                if cnt >= 0:
                   ans += 1
            return ans
        ans = 0
        for i in range(97,123):
            ans = max(ans,trans(chr(i)))
        return ans