Javascript: найдите длину самой длинной подстроки уникальных символов - PullRequest
Новая
       13

Javascript: найдите длину самой длинной подстроки уникальных символов

0 голосов
/ 12 июня 2019

У меня есть следующая проблема: мне нужно выяснить длину самой длинной подстроки уникальных символов.

например, у меня есть строка thequickbrownfoxjumpsoveralazydog, и я ожидаю получить 14 (длина thequickbrownf)

Здесь я нашел много тем, связанных с этой темой, но, похоже, я не могу перевести эти решения (если они есть) в Javascript.

Не могли бы вы?ребята, помогите мне с этим?Заранее спасибо миллион!

Ответы [ 3 ]

1 голос
/ 12 июня 2019

Учитывая (на основании вашего комментария), что вы на самом деле не получили алгоритмы, которые вам удалось найти, я предоставил свой код с пошаговыми пояснениями.

Основная концепция - пробежатьстрока, смещая один символ вправо каждый раз, когда вы находите дубликат, и сравнивая длину этих подстрок уникального символа, чтобы найти самую длинную: 

//input string
const src = 'thequickbrownfoxjumpsoveralazydog';
//iterate through characters
const longestUniqueSub = str => [...str].reduce((res, char, idx, self) => {
  //find first occurence of the 'char'
  const charPos = self.indexOf(char, res.anchor);
  //if didn't occur before and more chars to check, move on
  if(charPos == idx && idx < self.length - 1) return res;
  //assign res.len and shift anchor otherwise
  return {
    len: Math.max(res.len, (charPos < idx ? idx - 1 : idx) - res.anchor + 1),
    anchor: charPos < idx ? charPos + 1 : res.anchor
  };
}, {anchor: 0, len: 0}).len
//output the result  
console.log(longestUniqueSub(src));
.as-console-wrapper {min-height: 100%}
1 голос
/ 03 июля 2019

Существующие ответы не работают правильно, так как они ищут только самые длинные уникальные подстроки, начиная с определенных позиций (начало строки и сразу после некоторых повторяющихся символов). Они дают правильный ответ для 'thequickbrownfoxjumpsoveralazydog', так как самая длинная уникальная подстрока находится в начале строки. Они не работают для строки типа 'zabzcd', где самая длинная строка начинается со второй позиции и имеет длину 5.

Это будет работать для всех случаев: 

const tests = [
  'thequickbrownfoxjumpsoveralazydog', // 14
  'zabzcd', // 5
  'zabzcdthequickbrownfox', // 15
];

console.log( tests.map( get_max_unique_substring_length ) );

function get_max_unique_substring_length ( str ) {
  let unique_str = '';
  let max_length = 0;

  for ( let i = 0; i < str.length; i++ ) {
    const char = str[i];
    const char_pos = unique_str.indexOf( char );
    if ( char_pos >= 0 )
      unique_str = unique_str.substr( char_pos + 1 );

    unique_str += char;
    max_length = Math.max( unique_str.length, max_length );
  }

  return max_length;
}
1 голос
/ 12 июня 2019

Один из вариантов - использовать Set, который вы сбрасываете при обнаружении дублирующего символа, который выполняется за O(N) время: 

const str = 'thequickbrownfoxjumpsoveralazydog';
let set = new Set();
let bestRecordSoFar = 0;
let currRecord = 0;
[...str].forEach((char) => {
  if (set.has(char)) {
    bestRecordSoFar = Math.max(bestRecordSoFar, currRecord);
    set = new Set();
    currRecord = 0;
  }
  set.add(char);
  currRecord++;
});

const best = Math.max(bestRecordSoFar, currRecord);
console.log(best);
...