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

Question

Assuming I only have this interface for the LRU Cache:

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

• the key is the character in the string, and the value is the last index the character is seen
• I initialize my LRU Cache to have a capacity of k+1, so that the last node in my cache represents the index right before the start of my substring

how would I solve the "longest substring with k unique characters" problem? https://www.geeksforgeeks.org/find-the-longest-substring-with-k-unique-characters-in-a-given-string/

I'm stuck on how would I would know which character to pass to the get method, so that I can update my current longest substring, as well as to reconstruct the susbtring.

For example: k=3, the string is dbaaccaaadbaa and the answer is bolded. Once the last bolded "a" is looked at, the cache should look like:

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

Answer 1

You pass every character or your string to put when you see it. Then you track the string as it goes until you get the first (k+1)-th character in that string and you have to decide which part of the string is to throw away to leave only k characters. There is when you call get to know which character is the closest to beginning (i.e. throwing which character would give you the longest string of k + 1 unique characters that you can track further)

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)