如何使用 LRU 缓存获取具有 k 个唯一字符的最长子字符串

Question

假设我只有这个用于 LRU 缓存的接口：

LRU(int size): get(char key): int put(char key, int value): void

key为字符串中的字符，value为该字符出现的最后一个索引
我将我的 LRU 缓存初始化为具有 k+1 的容量，以便我的缓存中的最后一个节点代表正好在我的子字符串开始之前的索引

如何解决 "longest substring with k unique characters" 问题？ https://www.geeksforgeeks.org/find-the-longest-substring-with-k-unique-characters-in-a-given-string/

我不知道如何知道将哪个字符传递给 get 方法，以便我可以更新我当前最长的子字符串，以及重建 susbtring。

例如：k=3，字符串为dbaaccaaadbaa，答案加粗。查看最后一个粗体 "a" 后，缓存应如下所示：

A: 8 C: 5, B: 1, D:0

Answer 1

当您看到每个字符或您的字符串时，您将其传递给 put。然后你跟踪字符串，直到你得到第一个 (k+1)-th 字符在该字符串中，你必须决定要丢弃字符串的哪一部分离开只有 k 个字符。当你调用 get 来知道哪个字符最接近开始时（即抛出哪个字符会给你最长的 k + 1 个唯一字符的字符串，你可以进一步跟踪）

https://jsfiddle.net/zyhh4bup/

const str = 'dbaaccaaadbaa'
const k = 3

const cache = {}
const lruPut = (char, index) => cache[char] = index
const lruGet = (char) => cache[char]

var longest = ''
var current = ''
var currentChars = {}

for (var i = 0; i < str.length; i++) {
  if (longest.length < current.length) {
   longest = current
  }
  currentChars[str[i]] = true;
  current += str[i];
  lruPut(str[i], i)
  if (Object.keys(currentChars).length > k ) {
    // we have to interrupt the sequence and start a new one
    // new sequence is started from the furtherst character
    var positions = Object.keys(currentChars).map(char => lruGet(char))
    var position = Math.min.apply(null, positions)
    // cutting the current sequence to remove first (k + 1)-th character
    var current = str.slice(position + 1, i + 1)
    delete currentChars [str[position]]
  }
}

console.log(longest)

如何使用 LRU 缓存获取具有 k 个唯一字符的最长子字符串

How to use an LRU Cache to get the longest substring with k unique characters

algorithm

interface

lru