题解 | #至多包含K种字符的子串# LRU解法

使用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;
    }
}