P2830. 斗地主

解题思路

比较常规的哈希表题目，但由于涉及到字符和数字之间的相互转换，即 "J"、"Q"、"K"、"A" 和数字 11、12、13、14 之间的相互转换，故代码比较长，需要细心完成。

数字和字母之间的映射

首先我们可以构建两个哈希表 convert_dic 和 convert_dic2，分别完成从数字映射到字母，以及从字母映射到数字的工作。

数据预处理

题目所给定的两行输入，分别代表手上已有的牌和已经出过的牌。题目要求判断的对手手上可能拥有的最长顺子，其实就是要计算除了上述两种情况的剩余所有情况。

由于我们知道在一副牌中，每种牌只有最多只有 4 张，我们可以很容易判断出剩余的牌的张数。我们可以把上述两种情况进行合并，储存在同一个哈希表 cnt_using_str 中，表示所有已经使用过的牌的个数。

再将 cnt_using_str 里的 key 转化为 int 类型，对应的 value 不变，储存在一个新的哈希表 cnt_using_num 中。使用 int 类型来储存数据，是因为这样做更加方便我们进行顺子的判断。

顺子的判断

在关于顺子的判断中，我们可以先初始化 3 个变量来维护整个过程。

由于顺子中包含的数字范围是 3 到 14，我们可以做一个从 3 到 14 的 for 循环。当 cnt_using_num[i] == 4 时，说明此时当前数字 i 已经完全用完，无法构成一个包含 i 的顺子。当 cnt_using_num[i] != 4 时，说明此时当前数字 i 还有剩余，有可能构成一个包含 i 的顺子（之所以说有可能，是因为还需要考虑顺子的长度至少为 5）。

因此当 cnt_using_num[i] != 4 时，我们可以令当前顺子长度 cur_length += 1，来表示当前可能存在的顺子长度增加。

而当 cnt_using_num[i] == 4 时，由于此时已经不构成包含 i 的顺子了，而在 i 之前的若干已经判断过的数字 i-cur_length, ..., i-3, i-2, i-1 是可能能够构成顺子的。

此时我们有可能要更新答案。如果 cur_length ≥ 5，且 cur_length ≥ max_length 的时候，我们要更新 ans 和 max_length。

在更新 ans 的时候，我们可以直接使用推导式结合前面构建的将数字转化为字母的哈希表 convert_dic2 来完成。而 max_length 要更新为当前已经得到的最长顺子长度 cur_length。

综上我们可以得到以下代码。

但是上述代码还存在一个小问题，就是当某一个以 A 为结尾（也就是 i = 14）的顺子存在的时候，我们是无法正确地更新答案的。这是一个非常常见的 边界值问题。

解决方案非常简单，我们只需要在遍历 i 的时候多遍历一个数字，不是遍历到 14 结束而是遍历到 15 结束。当 i = 15 时，我们令其也进入更新答案的 if 分支，这样就可以将 A 作为结尾的顺子进行更新了。修改代码为：

这种做法非常类似于做 滑窗问题 的时候，我们在数组或字符串末尾多填充一个占位元素或空字符，以处理包含最后一个元素的窗口的情况。大家可以多多总结比较。

复杂度分析 设两行输入的牌的总张数为 n。由于一副牌只有 54 张，n 本身有常数上界，但按输入规模看各步骤如下：

• 拆分两行输入并用 Counter 统计已用牌数：O(n)。
• 删除 "2"、"B"、"C" 三个键与构建数字、字母互转的两张映射表：点数种类固定，O(1)。
• 把字符串键转成数字键：键的种类至多 12 种（3 到 A，2 和大小王已删除），O(1)。
• 顺子扫描：for 循环固定从 3 跑到 15，共 13 轮，每轮做常数次判断；命中更新答案时的 join 拼接至多 12 张牌，也是常数开销。

总时间复杂度 O(n)，即读入和计数这一遍；空间复杂度 O(1)，哈希表键的数量被点数种类钉死，与输入规模无关。