根据搜索结果，以下是 LeetCode 3563. Lexicographically Smallest String After Adjacent Removals 的 Java 实现。
题目理解
- "连续" 定义：字母表中绝对差为 1 或 25 的两个字母（即 `a↔b`, `b↔c`, ..., `y↔z`, `z↔a`）
- 每次操作可删除任意一对相邻且连续的字母
- 删除后字符串会压缩，两边的字符会重新相邻
- 目标：经过任意次操作后，得到字典序最小的字符串
核心思路
使用 区间 DP：
1. `dp[i][j]` 表示子串 `s[i..j)` 经过若干次删除操作后能得到的最小字典序字符串
2. 初始化 `dp[i][i] = ""`（空串）
3. 对于每个区间 `s[i..j)`：
- 保留 `s[i]`：结果为 `s[i] + dp[i+1][j]`
- 删除 `s[i]`：需要找到 `s[k]`（`i < k < j`），使得 `s[i]` 和 `s[k]` 连续，且中间部分 `s[i+1..k)` 能被完全删空（即 `dp[i+1][k] == ""`），结果为 `dp[k+1][j]`
- 取两者中字典序更小的
时间复杂度：O(n³)，空间复杂度：O(n²)
Java 实现
```java
class Solution {
public String lexicographicallySmallestString(String s) {
final int n = s.length();
// dp[i][j]: 子串 s[i..j) 经过若干次删除后能得到的最小字典序字符串
String[][] dp = new String[n + 1][n + 1];
// 初始化：空区间结果为 ""
for (int i = 0; i <= n; ++i) {
dp[i][i] = "";
}
// 按区间长度从小到大计算
for (int d = 1; d <= n; ++d) {
for (int i = 0; i + d <= n; ++i) {
final int j = i + d;
// 情况1：保留 s[i]，结果为 s[i] + dp[i+1][j]
String minString = s.charAt(i) + dp[i + 1][j];
// 情况2：尝试删除 s[i]
// 需要找到 s[k] 与 s[i] 连续，且 s[i+1..k) 能被完全删空
for (int k = i + 1; k < j; ++k) {
if (isConsecutive(s.charAt(i), s.charAt(k)) && dp[i + 1][k].isEmpty()) {
String candidate = dp[k + 1][j];
if (candidate.compareTo(minString) < 0) {
minString = candidate;
}
}
}
dp[i][j] = minString;
}
}
return dp[0][n];
}
// 判断两个字母是否"连续"（在循环字母表中差1或25）
private boolean isConsecutive(char a, char b) {
int diff = Math.abs(a - b);
return diff == 1 || diff == 25;
}
}
```
代码说明
要点 说明
`dp[i][j]` 左闭右开区间 `s[i..j)` 的最小字典序结果
`dp[i][i] = ""` 空子串结果为空字符串
保留 `s[i]` `s.charAt(i) + dp[i+1][j]`
删除 `s[i]` 需找到 `s[k]` 与 `s[i]` 连续，且 `dp[i+1][k]` 为空（中间全删完），然后取 `dp[k+1][j]`
`isConsecutive` `diff == 1` 处理 `a-b`, `b-c` 等；`diff == 25` 处理 `z-a` 的循环情况
复杂度分析
- 时间复杂度：O(n³)，外层两重循环遍历所有 O(n²) 个区间，内层循环最多 O(n) 次查找 `k`
- 空间复杂度：O(n²)，存储 `dp` 数组
如需优化，可以考虑使用记忆化搜索 + 缓存的方式，或者进一步优化状态转移。
