Kimi LeetCode 3485. 删除元素后 K 个字符串的最长公共前缀 C++实现

以下是 LeetCode 3485 删除元素后 K 个字符串的最长公共前缀 的 C++ 实现。

核心思路（排序法）

参考 灵神（灵茶山艾府）的做法：

1. 排序后连续 k 个字符串的 LCP 最优：将 `words` 按字典序排序，任意 k 个字符串的最长公共前缀最大值，一定来自某个连续的 k 个字符串子数组。且该子数组的 LCP 等于首尾两个字符串的 LCP。
2. 预处理全局最大/次大 LCP：遍历所有长度为 k 的窗口，计算每个窗口首尾的 LCP，记录：
- `mx`：最大 LCP 值
- `mx2`：次大 LCP 值
- `mx_i`：最大 LCP 对应的窗口起始下标（在排序后的数组中）
3. 分类讨论：
- 若移除的字符串不在 `mx` 窗口内 → 答案为 `mx`
- 若移除的字符串在 `mx` 窗口内 → 该窗口被破坏，答案为 `mx2`
4. 边界：若 `k >= n`，移除一个后剩余不足 k 个，全填 `0`。

```cpp
class Solution {
public:
vector<int> longestCommonPrefix(vector<string>& words, int k) {
int n = words.size();

// 边界：移除一个后只剩 n-1 个，若 n-1 < k 则全为 0
if (k >= n) {
return vector<int>(n, 0);
}

// 1. 按字符串字典序对下标排序
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b) {
return words[a] < words[b];
});

// 2. 辅助函数：计算两个字符串的 LCP 长度
auto lcp = [&](const string& s, const string& t) -> int {
int i = 0;
int maxLen = min(s.size(), t.size());
while (i < maxLen && s[i] == t[i]) {
i++;
}
return i;
};

// 3. 遍历所有长度为 k 的窗口，找 mx, mx2, mx_i
int mx = 0; // 最大 LCP
int mx2 = 0; // 次大 LCP
int mx_i = 0; // 最大 LCP 窗口的起始下标

for (int i = 0; i <= n - k; i++) {
int len = lcp(words[idx[i]], words[idx[i + k - 1]]);
if (len > mx) {
mx2 = mx;
mx = len;
mx_i = i;
} else if (len > mx2) {
mx2 = len;
}
}

// 4. 构建答案
vector<int> ans(n, mx);
// 属于最大 LCP 窗口 [mx_i, mx_i + k - 1] 的原始下标，答案改为 mx2
for (int i = mx_i; i < mx_i + k; i++) {
ans[idx[i]] = mx2;
}

return ans;
}
};
```

复杂度分析

指标 复杂度
时间 `O(n log n + 总字符数)` — 排序 `O(n log n)`，所有 LCP 计算的总比较次数受限于字符串总长度（`≤ 10^5`）
空间 `O(n)` — 下标数组 + 答案数组

说明

- 排序时只排下标，不移动原字符串，保证能追溯到每个元素的原始位置。
- `lcp` 函数直接按字符比较（题目保证全为小写英文字母）。
- 当 `mx` 窗口内有多个相同字符串时，移除其中一个可能导致窗口内仍剩 `k` 个相同字符串，但按照排序后的窗口定义，该特定窗口已被破坏；此时答案退化为 `mx2`，这在题解中已被证明是正确的（若 `mx2` 与 `mx` 有交集，则 `mx2` 一定是 `mx` 的前缀，仍能满足）。