如何用指定接口的LRU Cache求解最多含k个不同字符的最长子串

首先得明确，我们用LRU Cache的核心目的，是同时记录每个字符的最后出现位置，并且能快速找到「最久没更新过最后出现位置的字符」——这个字符就是我们收缩窗口的关键。你把容量设为k+1的思路非常巧妙，这相当于给窗口留了个“预警位”：当缓存里挤进来k+1个不同字符时，就说明当前窗口的不同字符数超标了，必须把最久没动静的那个字符踢出去，同时调整窗口的左边界。

接下来一步步拆解具体做法，解决你困惑的get方法使用问题：

初始化准备 #

• 创建一个容量为k+1的LRU Cache实例；
• 定义两个变量：left（当前窗口的左边界索引，初始为0），max_len（记录最长子串的长度，初始为0）。

遍历字符串的每个字符（索引为i） #

假设当前处理的字符是c：

1. 调用put(c, i)更新缓存

   • 如果c已经在缓存里，这会把它的最后出现索引更新为当前的i，同时把它移到LRU的头部（标记为最近访问过）；
   • 如果c不在缓存里，缓存会把它加进去；如果此时缓存已满（已有k+1个不同字符），LRU会自动把最久没被更新的字符（也就是LRU链表尾部的那个）从缓存里删掉。

2. 调整窗口左边界，确保窗口内不同字符数≤k
   这就是你困惑的核心点：怎么确定调整后的左边界？其实我们不需要乱猜传哪个字符给get，而是要瞄准LRU淘汰的那个字符——当缓存因为新增c而淘汰了某个字符old_c时，old_c的最后出现索引就是窗口里最靠左的有效位置，所以我们要把left更新为old_c的索引 + 1（因为从left到old_c的索引这段里，old_c不会再出现了，窗口左边界可以直接移到它的下一位）。

   要是你的LRU接口没返回被淘汰的条目也没关系：因为每次put都会把当前字符移到头部，LRU的尾部节点对应的字符，就是最后出现索引最小的那个。只要能拿到尾部节点的key，调用get(key)就能得到那个最小索引，进而更新left。

3. 更新最长子串长度
   每次调整完窗口后，计算当前窗口的长度i - left + 1，如果比max_len大，就更新max_len。

用你给的例子验证（k=3，字符串dbaaccaaadbaa） #

当遍历到第8个索引的a时：

• 缓存里存的是A:8、C:5、B:1、D:0（容量4=3+1），此时窗口左边界是1（之前淘汰D时，把left设为0+1=1）；
• 当前窗口是从1到8，长度为8，这就是我们要找的最长子串长度。

当继续遍历后面的d（索引9）时：

• 调用put('D',9)，因为D已在缓存中，所以更新它的索引为9并移到LRU头部；
• 此时缓存里的条目是D:9、A:8、C:5、B:1，窗口内不同字符有4个，超过k=3；
• 找到LRU尾部节点的key是B，调用get('B')得到1，把left更新为1+1=2；
• 窗口长度变为8，和之前的max_len一致，无需更新。

总结一下，get方法主要是在我们需要获取某个字符的最后出现索引时使用——尤其是当我们需要找到LRU尾部节点对应字符的索引，以此调整窗口左边界的时候，就传入那个尾部字符的key，调用get拿到索引后更新left即可。

内容的提问来源于stack exchange，提问作者K. E. P. O