题解 | #至多包含K种字符的子串# LRU解法
至多包含K种字符的子串
https://www.nowcoder.com/practice/04c926ef687340c3842a72edb5c23ede
使用LRU确定需要移除的字符最后出现的位置。
using System; using System.Collections.Generic; public class KV { public int key; public int value; } public class LRU { public LinkedList<KV> list = new LinkedList<KV> (); public Dictionary < int, LinkedListNode<KV>>dict = new Dictionary < int, LinkedListNode<KV>> (); public int Count = 0; public bool Set(int key, int value) { if (dict.TryGetValue(key, out LinkedListNode<KV> node)) { node.Value.value = value; list.Remove(node); list.AddLast(node); return true; } else { list.AddLast(new KV() { key = key, value = value, }); node = list.Last; dict[key] = node; Count++; return false; } } public int RemoveFirst() { var node = list.First; list.RemoveFirst(); dict.Remove(node.Value.key); Count--; return node.Value.value; } } class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @param k int整型 * @return int整型 */ public int longestSubstring (string s, int k) { LRU lru = new LRU(); int maxLength = 0; int left = -1; for (int i = 0; i < s.Length; i++) { var c = s[i]; if (lru.Set(c, i)) { } else { if (lru.Count > k) { left = lru.RemoveFirst(); } } maxLength = Math.Max(maxLength, i - left) ; } return maxLength; } }