2901. 最长相邻不相等子序列 II

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 3.3k 阅读时长 ≈ 11 分钟

考点

  • LIS
  • 位运算
  • 状态压缩
  • 贪心

思路

0. 题意抽象

给定：

  • words[0..n-1]：字符串数组
  • groups[0..n-1]：组号数组

需要从左到右选出一个子序列（保持原相对顺序），使得相邻两项同时满足：

  1. 组号不同：groups[a] != groups[b]
  2. 单词长度相同，且恰好一处字符不同（汉明距离为 1）

目标：子序列长度最大，并输出任意一个最大解的单词序列。

后文记 L 为单词平均长度（本题上界很小，但讲义不依赖具体上界）。

1. 解法一：朴素 DP

1.1 状态设计

定义：

  • \(f[i]\)：以第 \(i\) 个单词结尾的最长合法子序列长度（这里用 1-based 的 i 表示实现更方便）
  • \(pre[i]\)：该最优状态来自哪个前驱下标（用于回溯）

初始化： 每个单词单独成序列，因此 \(f[i]=1\)， \(pre[i]=0\)。

1.2 转移

对每个 \(i\)，枚举所有 $j。若：

  • groups[i-1] != groups[j-1]
  • words[i-1] 与 words[j-1] 长度相等且恰好一处不同

则可转移： \[ f[i] = \max(f[i],\, f[j] + 1) \] 并同步更新 pre[i] = j。

1.3 判定函数（恰好一处不同）

检查逻辑：

  • 若长度不同，直接 false
  • 扫一遍字符，计数 diff
  • diff 超过 1 就提前 false
  • 最终返回 diff == 1

1.4 复杂度

  • 时间复杂度：对每个 \(i\) 枚举 \(j\)，并进行一次 \(O(L)\) 的比较 \[ O(n^2 \cdot L) \]

  • 空间复杂度： \[ O(n) \]

1.5 AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    static const int maxn = 1e3 + 5;

    // 判断两个字符串是否长度相同且恰好一个字符不同
    bool d(string& a, string& b) {
        if (a.size() != b.size()) return false;
        int diff = 0;
        for (int i = 0; i < (int)a.size(); ++i) {
            if (a[i] != b[i]) {
                if (diff) return false; // 已经有过一次不同了，再不同就失败
                ++diff;
            }
        }
        return diff == 1;
    }

    vector<string> getWordsInLongestSubsequence(vector<string>& words,
                                                vector<int>& groups) {
        int f[maxn], pre[maxn];
        int n = (int)words.size();
        int bestLen = 0, bestIdx = 0;

        for (int i = 1; i <= n; ++i) {
            f[i] = 1;      // 单点序列
            pre[i] = 0;    // 无前驱

            // 枚举所有前驱 j<i
            for (int j = i - 1; j >= 1; --j) {
                if (groups[i - 1] != groups[j - 1] &&
                    d(words[i - 1], words[j - 1]) &&
                    f[j] + 1 > f[i]) {
                    f[i] = f[j] + 1;
                    pre[i] = j;
                }
            }

            if (f[i] > bestLen) {
                bestLen = f[i];
                bestIdx = i;
            }
        }

        // 回溯构造答案
        vector<string> ans;
        while (bestIdx) {
            ans.push_back(words[bestIdx - 1]);
            bestIdx = pre[bestIdx];
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

1.6 易错点

  • diff 的逻辑：要确保最终是 diff == 1，不是 <=1
  • 索引：代码用 1-based 的 dp 数组，下标对应 words[i-1]

2. 解法二：模式串（占位符/涂黑）+ 哈希 DP（从“数组写法”到“四变量”）

第二种方法的核心不是“写 hash”，而是重新组织状态： 把“只差一位”这一约束转化为“共享同一个模式串（pattern）”。

2.1 为什么要做 pattern？

对于两个等长字符串 \(A\) 与 \(B\)，它们“恰好一处不同”等价于：

存在一个位置 \(p\)，使得删掉（忽略）第 \(p\) 位后，剩余字符完全相同。

换句话说，如果把第 \(p\) 位用一个特殊符号标记（占位），那么：

  • \(A\) 在 \(p\) 位占位后得到 pattern
  • \(B\) 在同一 \(p\) 位占位后也得到同一个 pattern

于是“能否相连”就变成： 是否存在某个 p，使两者占位后的 pattern 相同。

3. 第一步：占位符模式串 + 数组状态（arr[26][2]）

这一段是重难点：为什么要 arr[26][2]，以及 top1/top2 为什么要按字母分 26 类。

3.1 占位符写法为什么还要分 26 类？

考虑固定一个 pattern，例如：

  • b_c（表示第 2 位被占位）

能产生这个 pattern 的原字符串可能是：

  • bac（占位位置原字母是 a）
  • bbc（占位位置原字母是 b）
  • bzc（占位位置原字母是 z）
  • ……

当处理当前单词 bac（占位位置字母为 a）时，合法前驱必须满足：

  • pattern 相同：都能变成 b_c
  • 但占位位置的原字母必须 不等于 a（否则前驱就是同一个单词或差 0 位）
  • 并且 group 不同

因此，对同一个 pattern，必须能够快速回答：

“在占位位置字母为 k 的候选里，dp 最大/次大是谁？”

于是就自然得到二维分类：

  • 第二维（26）：占位位置的原字母 k
  • 第三维（2）：该字母下的 top1 / top2（为了 group 不同的备胎）

这就是 arr[26][2] 的来源。

3.2 数组状态的语义（非常重要）

对某个 pattern-key（比如 b_c），定义：

  • arr[k][0]：占位位置原字母是第 k 个字母（0..25）时，dp 最大的候选
  • arr[k][1]：同一字母 k 下，dp 次大的候选（通常用于 group 冲突时兜底）

每个元素里要存至少三样信息：

  • dp：该候选的 dp 值
  • grp：该候选的 group
  • idx：该候选来自 words 的下标（用于回溯）

3.3 top1/top2 的维护逻辑（数组版）

对每个到来的单词 i，在每个 pattern、每个字母 k 下，都要做一次“插入/更新”：

  • 如果新候选 group 与 top1 同组：只尝试提升 top1
  • 如果新候选 group 与 top2 同组：只尝试提升 top2；若top2大于top1，两者交换位置
  • 否则说明新候选与top1和top2均不同组：
    • 若 dp 更大 → 新候选成为 top1，旧 top1 下沉为 top2
    • 否则若 dp 比 top2 大 → 更新 top2

易错点：

  • top2 最好与 top1 的 group 不同，否则“备胎无效”
  • 更新顺序要谨慎，避免覆盖丢失旧 top1

3.4 数组版的典型瓶颈

数组版查询时，某个 pattern 命中后仍需要：

  • 扫 k=0..25（排除当前字母）
  • 每个 k 看 top1/top2
  • 常数大 + value 大（52 个 entry）

因此即使渐进上看似更优，在本题规模下不一定跑赢朴素 \(n^2\)。

3.5 AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
class Solution {
public:
    static const int maxn = 1e3 + 5;

    struct PrevState {
        int dp = 0;  // 当前最长长度
        int grp = 0; // 所属 group
        int idx = 0; // 对应单词下标
    };

    struct Node {
        PrevState arr[26][2];
    };

    unsigned long long encode(const string& s) {
        unsigned long long res = 0;
        for (int i = 0; i < (int)s.size(); ++i)
            res |= (s[i] == '_' ? 26ULL : (unsigned long long)(s[i] - 'a'))
                   << (5 * i);
        res |= 1ULL << (5 * s.size()); // 长度哨兵
        return res;
    }

    unsigned long long hole(unsigned long long s, int i) {
        return (s & ~(31ULL << (5 * i))) | (26ULL << (5 * i));
    }

    vector<string> getWordsInLongestSubsequence(vector<string>& words,
                                                vector<int>& groups) {
        int n = words.size(), f[maxn], pre[maxn], mx_idx = 0, mx = 0;
        unordered_map<unsigned long long, Node> mp;

        for (int i = 1; i <= n; ++i) {
            int g = groups[i - 1];
            f[i] = 1;
            pre[i] = 0;

            unsigned long long base = encode(words[i - 1]);
            int m = words[i - 1].size();

            // 查询阶段
            for (int j = 0; j < m; ++j) {
                auto it = mp.find(hole(base, j));
                if (it == mp.end())
                    continue;

                Node& node = it->second;
                int pos = words[i - 1][j] - 'a';

                for (int k = 0; k < 26; ++k) {
                    if (k == pos)
                        continue;

                    PrevState& a = node.arr[k][0];
                    if (g != a.grp && a.dp + 1 > f[i]) {
                        f[i] = a.dp + 1;
                        pre[i] = a.idx;
                        continue;
                    }

                    PrevState& b = node.arr[k][1];
                    if (g != b.grp && b.dp + 1 > f[i]) {
                        f[i] = b.dp + 1;
                        pre[i] = b.idx;
                    }
                }
            }

            if (f[i] > mx) {
                mx = f[i];
                mx_idx = i;
            }

            // 更新阶段
            for (int j = 0; j < m; ++j) {
                Node& node = mp[hole(base, j)];
                int k = words[i - 1][j] - 'a';

                PrevState& a = node.arr[k][0];
                PrevState& b = node.arr[k][1];
                int dp = f[i];

                if (g == a.grp) {
                    if (dp > a.dp)
                        a = {dp, g, i};
                } else if (g == b.grp) {
                    if (dp > b.dp) {
                        b = {dp, g, i};
                        if (b.dp > a.dp)
                            swap(a, b);
                    }
                } else {
                    if (dp > a.dp) {
                        b = a;
                        a = {dp, g, i};
                    } else if (dp > b.dp && g != a.grp) {
                        b = {dp, g, i};
                    }
                }
            }
        }

        vector<string> ans;
        for (int i = mx_idx; i; i = pre[i])
            ans.push_back(words[i - 1]);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

4. 第二步：从 arr[26][2] 降维到 “每个 key 只存 top1/top2”（四变量思想）

这是必须详细讲的另一个重点：为什么可以把 26 类完全删掉？

4.1 关键变化：pattern-key 的构造从“占位符”变成“涂黑 11111”

与其把占位位写成某个合法字母编码（如 26），更好的做法是：

  • 用 5-bit 全 1：11111（十进制 31）作为“涂黑符”
  • 因为正常字母只会编码到 0..26 或 1..26，不会等于 31 所以 31 是一个“域外标记”，不会和正常字符混淆。

这样，对单词的第 pos 位涂黑得到 key： \[ key = base \; \text{OR} \; (31 \ll (5 \cdot pos)) \] 这一步非常关键：

  • 用 OR 就能生成 pattern-key（不用先清位再写入）
  • “涂黑符”保证 pattern-key 表达的是“这一位不关心”

4.2 为什么此时不再需要 arr[26][2]？

对于某个固定的涂黑 key：

  • 被涂黑的位 pos 已固定
  • 其余所有位（pos 之外）必须完全相同，否则 key 不可能相等

因此，同一个 key 下的所有候选都满足：

它们与当前单词的差异位置只能是 pos（最多差这一位）

在题目保证 words 不重复（LeetCode 本题一般如此）或实现中用下标顺序保证不会自环时，实际上就能认为：

命中同一个涂黑 key 的“其他候选”，就是“可在 pos 处形成一位差异”的候选集合。

此时，真正需要额外过滤的只剩：

  • group 不同

于是对每个 key，只要维护：

  • top1（dp 最大的候选）
  • top2（dp 次大的候选，且尽量不同 group）

也就是所谓“4 个核心变量”：

  • dp1, idx1
  • dp2, idx2

为了 O(1) 判断 group 冲突，实践中额外把 group 也一起存（但本质仍是 top1/top2 两条记录）。

5. 第三步：位运算实现细节（编码、哨兵、优先级与坑）

5.1 5-bit 槽位编码

将字符串编码为一个 64-bit 整数：

  • 第 i 个字符占据 bit 区间 \([5i, 5i+4]\)
  • 编码值落在 0..31 之间

常见编码方案有两种：

  • 'a'..'z' -> 0..25 或 1..26
  • 额外用 31 当涂黑符

5.2 长度哨兵（必须强调）

如果字符编码允许出现 0（例如 'a'->0），不同长度可能发生 key 冲突（尾部 0 不贡献）。 因此需要额外设置一位“终止标记”： \[ res \; \text{OR}= 1 \ll (5 \cdot |s|) \] 这保证不同长度的编码一定不同。

当前第二份 AC（四变量版）已经加入长度哨兵，这是稳健做法。

5.3 OR 涂黑为什么快？

涂黑（置 31）可以用：

  • base | (31ULL << shift)

比“清位再写入”少了 & ~mask 的一步，且表达式更短，常数更小。

5.4 易错点清单（位运算类）

  • 移位优先级：建议写成 x << (5 * i) 加括号，避免读者误解
  • 负移位：pos 必须是 0-based；不要出现 i-1
  • 类型提升：移位前最好确保是 ULL，避免 int 左移 UB 风险
  • 哨兵位不应被 mask 覆盖：涂黑只作用于字符槽，哨兵位在 5*len，两者不冲突

6. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
class Solution {
 public:
  using ull = unsigned long long;
  static const int maxn = 1e3 + 5;

  // 对每个 pattern-key，只维护两条候选（top1/top2）
  // - top1：dp 最大的候选
  // - top2：dp 次大的候选（尽量与 top1 group 不同，便于 group 冲突时兜底）
  struct Best2 {
    int dp1 = 0, idx1 = -1, grp1 = -1;  // 最优
    int dp2 = 0, idx2 = -1, grp2 = -1;  // 次优
  };

  // 5-bit 编码 + 长度哨兵
  // 说明：
  // 1) 每个字符占 5 bit，放在 (5*i) 的槽位
  // 2) 这里用 (ch & 31) 得到 1..26（对 'a'..'z'）
  // 3) res |= 1<<(5*len) 加入长度哨兵，防止不同长度碰撞
  static inline ull encodeWord(const string& s) {
    ull res = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
      ull v = (ull)(s[i] & 31);     // 'a'..'z' -> 1..26
      res |= (v << (5 * i));
    }
    res |= (1ULL << (5 * (int)s.size())); // 长度哨兵
    return res;
  }

  // “涂黑”第 pos 位：把该 5-bit 槽置成 11111(31)
  // 说明：用 OR 即可，因为 31 覆盖该槽位全部 bit
  static inline ull blackAt(ull base, int pos) {
    return base | (31ULL << (5 * pos));
  }

  // 用新候选 (dp, grp, idx) 更新该 key 对应的 top1/top2
  // 维护不变量：
  // - top1.dp >= top2.dp
  // - 尽量让 top2.grp != top1.grp（否则备胎无效）
  static inline void relax(Best2& st, int dp, int grp, int idx) {
    if (st.idx1 == -1) {  // 第一次插入
      st.dp1 = dp; st.grp1 = grp; st.idx1 = idx;
      return;
    }

    // 同组：只能尝试提升 top1（否则会让 top1/top2 同组，备胎失效）
    if (grp == st.grp1) {
      if (dp > st.dp1) {
        st.dp1 = dp;
        st.idx1 = idx;
      }
      return;
    }

    // 不同组：可能成为新 top1
    if (dp > st.dp1) {
      // 旧 top1 下沉为 top2
      st.dp2 = st.dp1; st.grp2 = st.grp1; st.idx2 = st.idx1;
      st.dp1 = dp;     st.grp1 = grp;     st.idx1 = idx;
      return;
    }

    // 尝试更新 top2（top2 也按“同组提升/异组替换”处理）
    if (st.idx2 == -1) {
      st.dp2 = dp; st.grp2 = grp; st.idx2 = idx;
      return;
    }
    if (grp == st.grp2) {
      if (dp > st.dp2) {
        st.dp2 = dp;
        st.idx2 = idx;
      }
    } else if (dp > st.dp2) {
      st.dp2 = dp;
      st.grp2 = grp;
      st.idx2 = idx;
    }

    // 保险：保持 top1 >= top2
    if (st.dp2 > st.dp1) {
      swap(st.dp1, st.dp2);
      swap(st.grp1, st.grp2);
      swap(st.idx1, st.idx2);
    }
  }

  vector<string> getWordsInLongestSubsequence(vector<string>& words,
                                              vector<int>& groups) {
    int n = (int)words.size();
    int f[maxn], pre[maxn];
    int mx = 0, mx_idx = 0;

    // key: 涂黑 pattern 的位压缩编码
    // val: 该 pattern 下的 top1/top2 最优候选
    unordered_map<ull, Best2> mp;

    for (int i = 1; i <= n; ++i) {
      int g = groups[i - 1];
      f[i] = 1;
      pre[i] = 0;

      const string& w = words[i - 1];
      int m = (int)w.size();
      ull base = encodeWord(w);

      // 查询：枚举所有涂黑位置 j，找能接到 i 的最佳前驱
      for (int j = 0; j < m; ++j) {
        ull key = blackAt(base, j);
        auto it = mp.find(key);
        if (it == mp.end()) continue;

        const Best2& st = it->second;

        // 只需保证 group 不同：
        // - 若 top1 group 不冲突，用 top1
        // - 否则尝试 top2
        if (st.idx1 != -1 && st.grp1 != g && st.dp1 + 1 > f[i]) {
          f[i] = st.dp1 + 1;
          pre[i] = st.idx1;
        } else if (st.idx2 != -1 && st.grp2 != g && st.dp2 + 1 > f[i]) {
          f[i] = st.dp2 + 1;
          pre[i] = st.idx2;
        }
      }

      if (f[i] > mx) {
        mx = f[i];
        mx_idx = i;
      }

      // 更新：把当前 i 作为候选写回每个涂黑 pattern-key
      for (int j = 0; j < m; ++j) {
        ull key = blackAt(base, j);
        Best2& st = mp[key];             // 若不存在会默认构造（idx1=-1 表示空）
        relax(st, f[i], g, i);
      }
    }

    // 回溯输出：从 mx_idx 沿 pre[] 走回去
    vector<string> ans;
    for (int i = mx_idx; i; i = pre[i]) ans.push_back(words[i - 1]);
    reverse(ans.begin(), ans.end());
    return ans;
  }
};