Hard
题目描述
给定一个长度为 n 的字符串 caption。好字幕是指每个字符都以至少 3 个连续出现的形式存在的字符串。
例如：
- “aaabbb” 和 “aaaaccc” 是好字幕。
- “aabbb” 和 “ccccd” 不是好字幕。
你可以执行以下操作任意次数：
选择一个索引 i（其中 0 <= i < n），并将该索引处的字符更改为：
- 字母表中紧邻的前一个字符（如果 caption[i] != ‘a’）
- 字母表中紧邻的后一个字符（如果 caption[i] != ‘z’）
你的任务是使用最少的操作次数将给定的字幕转换为好字幕，并返回结果。如果有多个可能的好字幕，返回其中字典序最小的一个。如果无法创建好字幕，返回空字符串 “"。
示例 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"
输出: ""
解释: 可以证明给定的字幕不能通过任何操作转换为好字幕。
约束条件：
- 1 <= caption.length <= 5 * 10^4
- caption 仅由小写英文字母组成
解题思路
这道题需要将字符串转换为"好字幕”，即每个字符都至少连续出现3次。我们需要用动态规划来解决。
核心思路：
状态定义：
dp[i][c][cnt]表示处理到第i个位置，当前字符为c，连续相同字符个数为cnt的最小操作次数。分段处理：由于好字幕要求每个字符至少连续出现3次，我们需要将字符串分成若干段，每段内字符相同且长度至少为3。
贪心策略：为了获得字典序最小的结果，我们优先尝试较小的字符。对于每个分段，尝试所有可能的字符，选择代价最小且字典序最小的方案。
转移方程：
- 如果当前字符与前一个相同，连续计数+1
- 如果不同，需要确保前一个分段长度至少为3，然后开始新分段
边界处理：
- 字符串长度小于3时，无法形成好字幕
- 最后一个分段也必须满足长度≥3的要求
算法流程：
- 使用三维DP记录状态
- 枚举每个位置可能的字符选择
- 计算操作代价（字符间距离）
- 确保每个分段长度至少为3
- 返回最优解，如果不存在则返回空字符串
时间复杂度主要来自于状态转移，需要仔细处理分段边界和字典序要求。
代码实现
class Solution {
public:
string minCostGoodCaption(string caption) {
int n = caption.length();
if (n < 3) return "";
// dp[i][c][cnt] = minimum cost to make first i chars valid,
// ending with char c appearing cnt consecutive times
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(26, vector<int>(n + 1, INT_MAX)));
vector<vector<vector<pair<int, int>>>> parent(n + 1, vector<vector<pair<int, int>>>(26, vector<pair<int, int>>(n + 1, {-1, -1})));
// Initialize
for (int c = 0; c < 26; c++) {
dp[1][c][1] = abs(caption[0] - ('a' + c));
}
for (int i = 1; i < n; i++) {
for (int c = 0; c < 26; c++) {
for (int cnt = 1; cnt <= n; cnt++) {
if (dp[i][c][cnt] == INT_MAX) continue;
int cost = abs(caption[i] - ('a' + c));
// Continue with same character
if (cnt + 1 <= n) {
if (dp[i + 1][c][cnt + 1] > dp[i][c][cnt] + cost) {
dp[i + 1][c][cnt + 1] = dp[i][c][cnt] + cost;
parent[i + 1][c][cnt + 1] = {c, cnt};
}
}
// Start new segment (only if current segment >= 3)
if (cnt >= 3) {
for (int nc = 0; nc < 26; nc++) {
int newCost = abs(caption[i] - ('a' + nc));
if (dp[i + 1][nc][1] > dp[i][c][cnt] + newCost) {
dp[i + 1][nc][1] = dp[i][c][cnt] + newCost;
parent[i + 1][nc][1] = {c, cnt};
}
}
}
}
}
}
// Find minimum cost ending
int minCost = INT_MAX;
int bestC = -1, bestCnt = -1;
for (int c = 0; c < 26; c++) {
for (int cnt = 3; cnt <= n; cnt++) {
if (dp[n][c][cnt] < minCost || (dp[n][c][cnt] == minCost && (bestC == -1 || c < bestC))) {
minCost = dp[n][c][cnt];
bestC = c;
bestCnt = cnt;
}
}
}
if (minCost == INT_MAX) return "";
// Reconstruct answer
string result(n, 'a');
int pos = n, curC = bestC, curCnt = bestCnt;
while (pos > 0 && parent[pos][curC][curCnt].first != -1) {
char ch = 'a' + curC;
for (int j = 0; j < curCnt; j++) {
result[pos - 1 - j] = ch;
}
pos -= curCnt;
auto p = parent[pos + curCnt][curC][curCnt];
curC = p.first;
curCnt = p.second;
}
return result;
}
};
class Solution:
def minCostGoodCaption(self, caption: str) -> str:
n = len(caption)
if n < 3:
return ""
# dp[i][c][cnt] = minimum cost to process first i characters
# ending with character c appearing cnt consecutive times
dp = [[[float('inf')] * (n + 1) for _ in range(26)] for _ in range(n + 1)]
parent = [[[(-1, -1)] * (n + 1) for _ in range(26)] for _ in range(n + 1)]
# Initialize first position
for c in range(26):
cost = abs(ord(caption[0]) - ord('a') - c)
dp[1][c][1] = cost
# Fill DP table
for i in range(1, n):
for c in range(26):
for cnt in range(1, n + 1):
if dp[i][c][cnt] == float('inf'):
continue
cost = abs(ord(caption[i]) - ord('a') - c)
# Continue same character
if cnt + 1 <= n:
new_cost = dp[i][c][cnt] + cost
if new_cost < dp[i + 1][c][cnt + 1]:
dp[i + 1][c][cnt + 1] = new_cost
parent[i + 1][c][cnt + 1] = (c, cnt)
# Start new segment (if current segment >= 3)
if cnt >= 3:
for nc in range(26):
new_cost = dp[i][c][cnt] + abs(ord(caption[i]) - ord('a') - nc)
if new_cost < dp[i + 1][nc][1]:
dp[i + 1][nc][1] = new_cost
parent[i + 1][nc][1] = (c, cnt)
# Find best ending
min_cost = float('inf')
best_c = best_cnt = -1
for c in range(26):
for cnt in range(3, n + 1):
if dp[n][c][cnt] < min_cost or (dp[n][c][cnt] == min_cost and (best_c == -1 or c < best_c)):
min_cost = dp[n][c][cnt]
best_c = c
best_cnt = cnt
if min_cost == float('inf'):
return ""
# Reconstruct result
result = ['a'] * n
pos, cur_c, cur_cnt = n, best_c, best_cnt
while pos > 0 and parent[pos][cur_c][cur_cnt][0] != -1:
ch = chr(ord('a') + cur_c)
for j in range(cur_cnt):
result[pos - 1 - j] = ch
pos -= cur_cnt
cur_c, cur_cnt = parent[pos + cur_cnt][cur_c][cur_cnt]
return ''.join(result)
public class Solution {
public string MinCostGoodCaption(string caption) {
int n = caption.Length;
if (n < 3) return "";
// dp[i][c][cnt] = minimum cost to process first i characters
int[,,] dp = new int[n + 1, 26, n + 1];
(int, int)[,,] parent = new (int, int)[n + 1, 26, n + 1];
// Initialize with max values
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 26; j++) {
for (int k = 0; k <= n; k++) {
dp[i, j, k] = int.MaxValue;
parent[i, j, k] = (-1, -1);
}
}
}
// Initialize first position
for (int c = 0; c < 26; c++) {
int cost = Math.Abs(caption[0] - ('a' + c));
dp[1, c, 1] = cost;
}
// Fill DP table
for (int i = 1; i < n; i++) {
for (int c = 0; c < 26; c++) {
for (int cnt = 1; cnt <= n; cnt++) {
if (dp[i, c, cnt] == int.MaxValue) continue;
int cost = Math.Abs(caption[i] - ('a' + c));
// Continue same character
if (cnt + 1 <= n) {
int newCost = dp[i, c, cnt] + cost;
if (newCost < dp[i + 1, c, cnt + 1]) {
dp[i + 1, c, cnt + 1] = newCost;
parent[i + 1, c, cnt + 1] = (c, cnt);
}
}
// Start new segment
if (cnt >= 3) {
for (int nc = 0; nc < 26; nc++) {
int newCost = dp[i, c, cnt] + Math.Abs(caption[i] - ('a' + nc));
if (newCost < dp[i + 1, nc, 1]) {
dp[i + 1, nc, 1] = newCost;
parent[i + 1, nc, 1] = (c, cnt);
}
}
}
}
}
}
// Find best ending
int minCost = int.MaxValue;
int bestC = -1, bestCnt = -1;
for (int c = 0; c < 26; c++) {
for (int cnt = 3; cnt <= n; cnt++) {
if (dp[n, c, cnt] < minCost || (dp[n, c, cnt] == minCost && (bestC == -1 || c < bestC))) {
minCost = dp[n, c, cnt];
bestC = c;
bestCnt = cnt;
}
}
}
if (minCost == int.MaxValue) return "";
// Reconstruct result
char[] result = new char[n];
int pos = n, curC = bestC, curCnt = bestCnt;
while (pos > 0 && parent[pos, curC, curCnt].Item1 != -1) {
char ch = (char)('a' + curC);
for (int j = 0; j < curCnt; j++) {
result[pos - 1 - j] = ch;
}
pos -= curCnt;
(curC, curCnt) = parent[pos + curCnt, curC, curCnt];
}
return new string(result);
}
}
var minCostGoodCaption = function(caption) {
const n = caption.length;
if (n < 3) return "";
let minCost = Infinity;
let bestResult = "";
// Try each character as the target for the entire string
for (let targetChar = 0; targetChar < 26; targetChar++) {
const char = String.fromCharCode(97 + targetChar);
let cost = 0;
for (let i = 0; i < n; i++) {
cost += Math.abs(caption.charCodeAt(i) - (97 + targetChar));
}
if (cost < minCost) {
minCost = cost;
bestResult = char.repeat(n);
}
}
// Try dynamic programming approach for more complex patterns
const dp = new Array(n).fill(null).map(() => new Array(26).fill(Infinity));
// Initialize first position
for (let c = 0; c < 26; c++) {
dp[0][c] = Math.abs(caption.charCodeAt(0) - (97 + c));
}
for (let i = 1; i < n; i++) {
for (let c = 0; c < 26; c++) {
const changeCost = Math.abs(caption.charCodeAt(i) - (97 + c));
// Try extending from previous character
for (let prevC = 0; prevC < 26; prevC++) {
if (dp[i-1][prevC] === Infinity) continue;
// Check if we can form a valid group
let canPlace = false;
if (c === prevC) {
canPlace = true;
} else {
// Check if we're starting a new group and previous groups are valid
canPlace = true;
}
if (canPlace) {
dp[i][c] = Math.min(dp[i][c], dp[i-1][prevC] + changeCost);
}
}
}
}
// Validate the result by checking groups
function isValidCaption(s) {
let i = 0;
while (i < s.length) {
let count = 1;
while (i + count < s.length && s[i + count] === s[i]) {
count++;
}
if (count < 3) return false;
i += count;
}
return true;
}
// Try all possible group arrangements
function solve(pos, current, currentCost) {
if (pos === n) {
if (isValidCaption(current) && currentCost < minCost) {
minCost = currentCost;
bestResult = current;
} else if (isValidCaption(current) && currentCost === minCost && current < bestResult) {
bestResult = current;
}
return;
}
if (currentCost >= minCost) return;
// Try each character
for (let c = 0; c < 26; c++) {
const char = String.fromCharCode(97 + c);
const cost = Math.abs(caption.charCodeAt(pos) - (97 + c));
// Try placing at least 3 consecutive characters
for (let len = 3; len <= Math.min(n - pos, 26); len++) {
if (pos + len <= n) {
let groupCost = 0;
let newCurrent = current;
for (let j = 0; j < len; j++) {
groupCost += Math.abs(caption.charCodeAt(pos + j) - (97 + c));
newCurrent += char;
}
if (currentCost + groupCost < minCost) {
solve(pos + len, newCurrent, currentCost + groupCost);
}
}
}
}
}
minCost = Infinity;
bestResult = "";
solve(0, "", 0);
return bestResult;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |