3441.变成好标题的最少代价

dp, https://leetcode.cn/problems/minimum-cost-good-caption/

给你一个长度为 n 的字符串 caption 。如果字符串中 每一个 字符都位于连续出现 至少 3 次 的组中，那么我们称这个字符串是好标题。

比方说：

"aaabbb" 和 "aaaaccc" 都是好标题。
"aabbb" 和 "ccccd" 都不是好标题。

你可以对字符串执行以下操作任意次：

选择一个下标 i（其中 0 <= i < n ）然后将该下标处的字符变为：

该字符在字母表中前一个字母（前提是 caption[i] != 'a' ）
该字符在字母表中后一个字母（caption[i] != 'z' ）

你的任务是用最少操作次数将 caption 变为好标题。如果存在多种好标题，请返回它们中 字典序最小 的一个。如果无法得到好标题，请你返回一个空字符串 "" 。

在字符串 a 和 b 中，如果两个字符串第一个不同的字符处，字符串 a 的字母比 b 的字母在字母表里出现的顺序更早，那么我们称字符串 a 的 字典序 比 b 小。如果两个字符串前 min(a.length, b.length) 个字符都相同，那么较短的一个字符串字典序比另一个字符串小。

示例 1：

输入：caption = "cdcd"

输出："cccc"

解释：

无法用少于 2 个操作将字符串变为好标题。2 次操作得到好标题的方案包括：

"dddd" ：将 caption[0] 和 caption[2] 变为它们后一个字符 'd' 。
"cccc" ：将 caption[1] 和 caption[3] 变为它们前一个字符 'c' 。

由于 "cccc" 字典序比 "dddd" 小，所以返回 "cccc" 。

示例 2：

输入：caption = "aca"

输出："aaa"

解释：

无法用少于 2 个操作将字符串变为好标题。2 次操作得到好标题的方案包括：

操作 1：将 caption[1] 变为 'b' ，caption = "aba" 。
操作 2：将 caption[1] 变为 'a' ，caption = "aaa" 。

所以返回 "aaa" 。

示例 3：

输入：caption = "bc"

输出：""

解释：

由于字符串的长度小于 3 ，无法将字符串变为好标题。

提示：

1 <= caption.length <= 5 * 104
caption 只包含小写英文字母。

python

class Solution:
    def minCostGoodCaption(self, caption: str) -> str:
        n = len(caption)
        if n < 3:
            return ""

        dp = [[0] * 26 for _ in range(n)]
        maxDp = [0] * n
        maxPos = [0] * n
        step = [[0] * 26 for _ in range(n)]

        # 初始化最后三个字符的dp数组
        for j in range(26):
            step[n - 3][j] = 3
            for k in range(n - 3, n):
                dp[n - 3][j] += abs(ord(caption[k]) - ord('a') - j)

        maxDp[n - 3] = dp[n - 3][0]
        for j in range(1, 26):
            if dp[n - 3][j] < maxDp[n - 3]:
                maxDp[n - 3] = dp[n - 3][j]
                maxPos[n - 3] = j

        # 填充dp数组
        for i in range(n - 4, -1, -1):
            for j in range(26):
                # remain
                step[i][j] = 1
                dp[i][j] = dp[i + 1][j] + abs(ord(caption[i]) - ord('a') - j)

                # change
                if i < n - 5:
                    newDp = maxDp[i + 3]
                    newPos = maxPos[i + 3]
                    for k in range(i, i + 3):
                        newDp += abs(ord(caption[k]) - ord('a') - j)
                    if newDp < dp[i][j] or (newDp == dp[i][j] and newPos < j):
                        step[i][j] = 3
                        dp[i][j] = newDp

            maxDp[i] = dp[i][0]
            for j in range(1, 26):
                if dp[i][j] < maxDp[i]:
                    maxDp[i] = dp[i][j]
                    maxPos[i] = j

        # 构建结果字符串
        res = []
        cur = 0
        curPos = maxPos[0]
        while cur < n:
            if step[cur][curPos] == 1:
                res.append(chr(curPos + ord('a')))
                cur += 1
                continue
            res.append(chr(curPos + ord('a')) * 3)
            cur += 3
            if cur < n:
                curPos = maxPos[cur]

        return ''.join(res)


if __name__ == '__main__':
    sol = Solution()
    print(sol.minCostGoodCaption("cdcd"))
    print(sol.minCostGoodCaption("aca"))
    print(sol.minCostGoodCaption("bc"))

3441.变成好标题的最少代价 ​

3441.变成好标题的最少代价