Как использовать LRU Cache для получения самой длинной подстроки с k уникальными символами - PullRequest
Новая
       17

Как использовать LRU Cache для получения самой длинной подстроки с k уникальными символами

0 голосов
/ 09 мая 2018

Предполагается, что у меня есть только этот интерфейс для LRU Cache:

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

  • ключ - это символ в строке, а значение - последний индекс, который символ видел
  • Я инициализирую свой LRU Cache, чтобы иметь емкость k + 1, так что последний узел в моем кэше представляет индекс непосредственно перед началом моей подстроки

как мне решить проблему "самой длинной подстроки с k уникальными символами"? https://www.geeksforgeeks.org/find-the-longest-substring-with-k-unique-characters-in-a-given-string/

Я застрял на том, как узнать, какой символ передать методу get, чтобы я мог обновить свою самую длинную подстроку, а также восстановить исходную строку.

Например: k = 3, строка d baaccaaa dbaa, и ответ выделен жирным шрифтом. После просмотра последней жирной буквы «а» кэш должен выглядеть следующим образом:

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

1 Ответ

0 голосов
/ 10 мая 2018

Вы передаете каждый символ или вашу строку в put, когда видите ее. Затем вы отслеживаете строку так, как она идет, пока не получите первый (k + 1) -й символ в этой строке, и вам нужно решить, какую часть строки отбросить, чтобы оставить только 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)
...