How to find substring palindrome? Task from frontend job interview | LeetCode | JavaScript

[@frontendscience]

Таймкоды: 00:00 Начало. 00:26 Уровень сложности на leetcode. 00:45 Разбираем условие задачи. 01:42 Зевнул🙂 02:29 Разбираем алгоритм решения. 05:42 Пишем код решения. 06:30 Пишем вспомогательную функцию expandFromCenter. 08:58 Находим максимальную длину палиндрома для каждого символа в строке. 10:58 Оптимизируем сложность алгоритма по памяти. 13:04 Проверяем работу алгоритма - запускаем!. 13:42 Сложность алгоритма. 14:01 Алгоритм Манакера. 14:18 Присылайте свои решения.

[@captain_kobi7476]

Крутое видео

[@frontendscience]

@@captain_kobi7476 Рад, что понравилось! :)

[@evgeniychip]

спасибо Сергей за контент, хорошо прокачался на литкоде благодаря тебе, так и до L5 фаанга недалеко, видосы смотрятся на одном дыхании

[@vadavur]

Здорово рассказано про память. Когда решал сам перед просмотром, алгоритм использовал схожий, но работал как раз-таки с подстроками. Плюс, пришлось вставить строчку-костылек на случай отсутствия палиндромов в строке. var longestPalindrome = function(s) { let longestPalindrome = ''; for (let i = 0; i < s.length - 1; i++){ if (s[i] === s[i + 1]) longestPalindrome = getLongestString(longestPalindrome, getPalindrome(s, i, i + 1)); if (s[i - 1] === s[i + 1]) longestPalindrome = getLongestString(longestPalindrome, getPalindrome(s, i - 1, i + 1)); } return getLongestString(longestPalindrome, s[0]); }; function getPalindrome(string, start, end) { while (string[start] && string[start] === string[end]) { start--; end++; } return string.slice(++start, end); } function getLongestString(string1, string2) { if (string1.length > string2.length) return string1; return string2; }

[@frontendscience]

Классно вышло!

[@holus-bolus]

Спасибо за такие видео. Смотрел одного английского блогера, он делал задачи с codewars, я чуть не уснул от его монотонности.

[@oleksandrlevchenko4028]

Спасибо вам, очень актуально для меня сейчас)

[@frontendscience]

Рад, что пригодилось! ;)

[@oxanananieva2643]

Cпасибо, очень полезный разбор задачи

[@frontendscience]

И Вам спасибо, что смотрите

[@maksymzhovtaniuk3958]

Спасибо за видео, очень интересное решение, даже не подумал, что так можно🤔 Кому интересно сделал примерно так (за 10-15 минут) const input1 = 'babad' // bab aba const input2 = 'cbbd' // bb const input3 = 'mississippi' // ississi const input4 = 'ac' // a c const longestPalindrome = function (str) { let maxCheckLength = 0 let tmp = 0 const palindrome = (text) => { text = text.toLowerCase().trim() return text === text.split('').reverse().join('') } for (let i = 0; i < str.length; i++) { for (let j = str.length - 1; j >= 0; j--) { if (str[i] === str[j]) { let check = str.slice(i, j + 1) tmp = check.length let checkResult = palindrome(check) if (checkResult && tmp >= maxCheckLength) { maxCheckLength = tmp console.log(`Result of checking string "${check}" ==== ${checkResult} with length ${maxCheckLength}`); } } } } return 0 } console.log(longestPalindrome(input1)) console.log(longestPalindrome(input2)) console.log(longestPalindrome(input3)) console.log(longestPalindrome(input4))

[@dmytrokoka3796]

Хороший разбор! А если не получается, то не волнуйся, если не работает. Если бы все всегда работало, у тебя бы не было работы.

[@maksbzr5655]

Очень крутая тема с решением задач

[@frontendscience]

Благодарим за поддержку!

[@ВадимБєк]

Было не просто но хоть как-то решить смог, изначально не было идей вобще но чуть глянув видео и услышав про 2 указателя подумал про два цикла и дальше делал сам, понимаю что алгоритм вышел нагруженным и в условие не попадаю но рад что смог хоть как-то сделать const longestPalindrome = str => { let palindromes = {}; for(let i = 0; i0;j--){ if(str[i] == str[j]){ let check = str.slice(i,1+j); let isPalindromebool = true; [...check].forEach((elem,index,array)=>{ elem == array[array.length - index - 1] ? elem : isPalindromebool = false; if(index == array.length -1 && isPalindromebool == true)palindromes[check.length] = str.slice(i,1+j); }) } } } let result = Object.values(palindromes); return result.sort((a,b)=> a-b)[0]; } Если есть советы по тому как можно улучшить код буду рад услышать их Теперь можно и решение посмотреть.

[@frontendscience]

Благодарю за решение! Идея интересная вышла. Собираешь все возможные палиндромы. Из оптимизации я бы наверное предложил хранить максимальный найденный до этого палиндром и если на новой итерации нашелся еще длиннее то заменять его в переменной. Просто сейчас все палиндромы (и его подчасти) хранятся в объекте и это большой удар по памяти ) PS: код надо подправить. В последних 2~ строках ошибка. вот так будет работать: let result = Object.keys(palindromes); return palindromes[result.sort((a,b)=> b-a)[0]];

[@stormd2902]

Спасибо за такие полезные видео Помогает

[@frontendscience]

И Вам спасибо, что смотрите! :) Это вдохновляет)

[@romanryaboshtan9270]

Я понял, как работает этот алгоритм, автор молодец

[@АрсаланБазаров-л4п]

Спасибо большое за годный контент!))

[@ОлегСелин-ш9ы]

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

[@frontendscience]

🤓 ))

[@zosyanax]

мой костылек на пыхе, с примерами Сергея работает, на остальном не тестил public function testPalindromSubstring( string $title ): string { $title = preg_replace( '/\W/', '', strtolower( $title ) ); $start = 0; $end = 0; if ( strlen( $title ) expand( $title, $i, $i + 1 ); } if ( $title[ $i + 1 ] === $title[ $i - 1 ] ) { $expand = $this->expand( $title, $i - 1, $i + 1 ); } if ( $expand[ 0 ] - $expand[ 1 ] >= $end - $start ) { [ $end, $start ] = $expand; } } return substr( $title, $start, $end ); } public function expand( string $title, int $start, int $end ): array { while ( $start >= 0 && $end < strlen( $title ) && $title[ $start ] === $title[ $end ] ) { $start--; $end++; } $start++; return [ $end - 1, $start ]; }

[@Kozmo969]

Крутое видео, спасибо большое!

[@maksudibr8637]

Большой рахмат!

[@frontendscience]

Ыраазы бул жакты

[@multiply87]

Спасибо, очень интересно и полезно)

[@frontendscience]

Ты прям пачками, я смотрю, задачи проходишь! Крутецки!))) Высылай решения!

[@multiply87]

@@frontendscience прости, конкретно вчера я их не решал, а смотрел в качестве развлекательного видео. Очень нравится видеть алгоритмы, которые раньше и вообразить не мог)

[@АрсаланБазаров-л4п]

thank you for your excellent content!))))

[@ИванКущ-р7с]

Просто лучший!!!

[@vadimman6140]

Увидел условия стало как-то не по себе, нус будем пробовать

[@frontendscience]

Успехов! Присылай потом решение!

[@EvilYou]

Задачу решил, но возникли интересные ситуации при отправке на leetcode. При первой проверке результат - Runtime error, так как в дополнительной функции, которая проверяет на палиндром, я преобразовывал строку в массив и обратно. При второй отправке оптимизировал эту функцию и leetcode зачел мое решение, но с весьма печальным результатом: Runtime: 6624 ms, faster than 5%. Ну и, наконец, при третьей, добавил выход из цикла когда получить палиндром длиннее было уже невозможно. Вот решение: function longestPalindrome(str) { let longest = null; let maxLength = 0; let current = ""; for (let i = 0; i < str.length; i++) { if (maxLength >= str.length - i) break; // если длиннее строки быть не может for (let j = i; j < str.length; j++) { current += str[j]; if (isPalindrome(current)) { if (current.length > maxLength) { maxLength = current.length; longest = current; } } } current = ""; } return longest; } function isPalindrome(s) { let half = Math.floor(s.length / 2); for (let i = 0; i < half; i++) { if (s[i] !== s[s.length - 1 - i]) return false; } return true; } Результат на leetcode: Runtime: 2004 ms, faster than 15.32% Конечно, решение далеко не из быстрых получилось. Поэтому сейчас начинаю смотреть решение из видео.

[@frontendscience]

Классно! Круто что сам решил! Благодарю за вариант!

[@EvilYou]

Суть решения: прохожусь циклом по строке и проверяю символы слева и справа. Если равны, проверяю дальше и тд. Второй вложенный цикл for делает то же самое, только если два символа встретились подряд. function longestPalindrome(s) { let result = s[0]; for (let i = 0; i < s.length; i++) { let currentStr = s[i]; let maxJ = Math.min(i + 1, s.length - i); // сколько до конца строки справа или слева if (result.length > maxJ * 2) break; // оптимизация, чтобы меньше проверять for (let j = 1; j < maxJ; j++) { let left = i - j; let right = i + j; if (s[left] !== s[right]) break; currentStr = s[left] + currentStr + s[right]; if (currentStr.length > result.length) { result = currentStr; } } if (s[i + 1] !== s[i]) continue; currentStr = ''; maxJ = Math.min(i + 1, s.length - 1 - i); for (let j = 0; j < maxJ; j++) { let left = i - j; let right = i + 1 + j; if (s[left] !== s[right]) break; currentStr = s[left] + currentStr + s[right]; if (currentStr.length > result.length) { result = currentStr; } } } return result; } На leetcode: Runtime: 105ms (Beats 59.34%). Решение из видео чуть быстрее: Runtime 100 ms.

[@СергейКозлов-н1л]

Сергей, а не могли бы указать, какие структуры данных необходимо 100% знать фронтенд-разработчику? И что делать, если прочитал условие задачи, но нет каких-то мыслей с чего начать решать, т.е. по сути нет идеи? Откуда брать это понимание, какой алгоритм нужно использовать?

[@frontendscience]

Олтичная идея для новго видео! :) Для фронтендера точно важно знать: строки, числа, объекты, массивы, сеты и мапы. Так как с этими структурами прийдется работать. А вот для прохождения суровых собеседований в большие компании понадобится знания еще таких структур: linked list, binary tree, graph, trie, stack, queue, min/max stack. Что касается самого алгоритма - то тут нужна практика. Надо начинать с задач попроще и повышать уровень сложности постепенно. С практикой прийдет понимание когда какой алгоритм использовать. Если есть задача которую не получается совсем решить - можно поискать решение (даже если на другом языке программирования будет) и просто посмотреть сам алгоритм. Но потом обязательно надо повторить самому и написать работающее решение.

[@Юлия-з5м2й]

Попробуй объяснить человеческим языком самому себе как бы ты это сделал как человек, чисто логически. Или уточке на утином) Разбей на подзадачи, совсем простые. Затем по пунктам приступай реализовывать уже в коде. И гугли по мере незнания конкретные моменты. Скорее всего идеи как написать нет на один маленький и совершенно определённый пункт подзадачи, который можно погуглить и применить к своему алгоритму решения.

[@Юлия-з5м2й]

Сначала будут выходить не очень быстрые и не самые изящные решения. Но по мере тренировки будешь уже видеть, что ага, с таким ты уже сталкивался и это можно покрутить так и сяк. И так найдёшь решение. Главное не останавливаться и не бросать

[@serverizedinov7942]

красава!

[@arslanaliisaev3324]

Ты лучший )

[@alicenNorwood]

1:54 - ваааааа, я ровно так же делаю, когда надо резко вернуть фокус

[@frontendscience]

)))) бро)

[@lycan9590]

Что-то хорошее )

[@Sleep88Walker]

Что-то хорошее

[@frontendscience]

Спасибо за поддержку

[@kirsan3103]

4 утра это ж середина рабочего дня разве нет? о_О XD

[@frontendscience]

😂

[@Юлия-ш9э4п]

Круто

[@dan1ar]

Это решение с ЛитКода, а я вот слышал, что можно решить через хеши и бинпоиск, вы знаете о таком алгоритме?

[@frontendscience]

Это мое решение) На Литкод я беру само условие задачи. Не слышал и пока не представляю, как именно эту задачу можно решить через хеши и бинарный поиск. Бинарный поиск это поиск одного конкретного элемента, а нам необходимо найти подстроку, которая является палиндромом.

[@АртемФролов-э2ч]

​@@frontendscience Здравствуйте! Тут идея про хеши и бин поиск в следующем: есть функция, у которой аргументы такие же, как и у Вашей expandFromCenter, только мы не проходимся циклом while, а используем бин поиск для нахождения самого длинного палиндрома, только я не совсем понимаю, как использовать хеши. Прикреплю псевдокод этой функции(тут она ищет кол-во палиндромов): int binarySearch(s : string, center, shift : int): //shift = 0 при поиске палиндрома нечётной длины, иначе shift = 1 int l = -1, r = min(center, s.length - center + shift), m = 0 while r - l != 1 m = l + (r - l) / 2 //reversed_hash возвращает хэш развернутой строки s if hash(s[center - m..center]) == reversed_hash(s[center + shift..center + shift + m]) l = m else r = m return r

[@sergeylysenko2866]

что-то хорошее

[@eghishemanukyan3021]

thanks

[@Юлия-з5м2й]

спать очень важно для мозга)

[@frontendscience]

- Вы хорошо высыпаетесь? - Куда?

[@frontendscience]

- Доктор, это что вы мне такое классное дали? - Поспать!

[@АнастасияДанилюк-я7л]

Вот такое есть(Не мое): function longest_palindrome(s) { var max = ''; for (var i = 0; i < s.length; i++) { for (var j = 0; j < 2; j++) { var left = i; var right = i + j; while (s[left] && s[left] === s[right]) { left--; right++; } if ((right - left - 1) > max.length) { max = s.substring(left + 1, right); } } } return max; }

[@frontendscience]

Ну алгоритм точно такой же - просто немного по другому реализован. Я специально вынес часть кода в отдельную функцию и сделал 2 переменные len1 и len2 чтобы было проще понять. По времени сложность алгоритма та же, а вот по памяти тут O(n) так как хранится вся подстрока.

[@frontendscience]

А теперь присылай свое решение ;)

[@АнастасияДанилюк-я7л]

@@frontendscience пока нос еще (у меня) не дорос. Понять что написано могу , но написать еще нет ... Доработать , подкорректировать

[@АнастасияДанилюк-я7л]

На codwerse эта задача 4 ku уровня .Из 4 уровня удалось решить пока 3 задачи.

[@userScKonov]

мне помогло)

[@frontendscience]

Рад, что было полезно!

[@wisarty]

Дякую

[@UlyanaVorobeva]

А что делать, если надо найти не подстроку палиндром, а подпоследовательность, т е можно удалять символы в середине, лишь бы был палиндром?)

[@das8434]

А как программа понимает что мы хотим от аргументов L, R ? Как она понимает, что под L и R мы подразумеваем указатель лево и право в строке ?

[@frontendscience]

Мы ведь сами задаем индексы элементов для этих указателей. Для L мы задаем индекс элемента слева, а для R - индекс элемента справа.

[@das8434]

@@frontendscience да но как мы задаём программе, что L это левый указатель, а R это правый ? В функции написано только что L >= 0, а R < s.length. Тоесть мы просто говорим программе что L меньше или равняется 0 и что R меньше длины s. Но мы не как не объясняем программе что L и R это правый и левый указатель в массиве и что они значат

[@frontendscience]

Мы вызываем функцию expandFromCenter и передаем в нее уже готовые L и R указатели в качестве аргументов. (Строки 11 и 12). Дальше на каждой итерации Левый указатель бежит в лево пока не дойдет до начала, а правый бежит вправо - пока не дойдет до конца массива (это если элементы равны друг другу на каждой итерации).

[@das8434]

@@frontendscience тоесть мы сначала пишем функцию expandFromCenter для указателей L и R, а позже ее подключаем к len1 и len 2 ?

[@frontendscience]

@@das8434 да именно так!

[@Dobermun]

Вау

[@verbychi3091]

Недосмотрев до конца, считал, что знаю алгоритм Манакера... недолго я прожил во лжи

[@frontendscience]

Смешно шутите :)

[@dad2863]

Почему при вводе hellow вывод llo

[@redmex176]

вывод ll

[@realkazakhit45]

[@ilovemama6997]

проверь на "ааа" не работает

[@frontendscience]

Смешно! А сам че не проверил? Ты удивишься - ведь все таки работает!

[@alexey731]

блин сложно..

[@frontendscience]

Рекомендую, если еще не видели предыдущие 2 задачи про палиндромы начать именно с них. Тогда эта станет понятней. На будущее я планирую снять еще видео с алгоритмом 2 указателя - думаю это поможет лучше разобраться и с это задачей тоже.

[@alexey731]

@@frontendscience Спасибо большое, сейчас посмотрю! А так задача очень полезная, хотелось бы ее осмыслить

[@frontendscience]

@@alexey731 Ну надеюсь я в видео все подробно разобрал, и что прийдет осмысление после просмотра предыдущих. :)

[@geimproberegov7350]

Помогите тупому учиться. ) я второй день не догоняю , как у нас передается в функции expandFromCenter наша середина, если у нас итерируется одни и те же элементы , так как мы передаем их через i . то есть L=0, R=0 и так далее. , почему к примеру в слове "babad" начинает while Отрабатывать именно на середине , если у нас и до середины элементы получается одинаковые a=a ..

[@react_js]

как я понял, expandFromCenter не начинает с середины, а с самого начала. потому что цикл for начинает i с нуля. а дальше i прибавляется. а R++ и L- -. и таким образом дальше идет. Непонятно почему он в слове babad середину показывает. там же i с нуля идет. ну да ладно

[@whiteguards43]

@@react_js так там услвоие L >= 0, если L === 0, то L-- это -1, что соотвественно прервет цикл while

[@mikhailblush5261]

отец, ты спишь вообще?

[@frontendscience]

Я как медведь - накапливаю!

[@eghishemanukyan3021]

если ты смотришь это сообщение то пожалуйста оставь свое мнение об этом решение мне очень интересно const longestPalindrome = function(s){ let str = ''; let arr = []; let res = [] for(let i = 0; i < s.length; i++) { str = s[i]; for(let j = i+1; j < s.length; j++) { str += s[j] if(isPalindrome(str)) { arr.push(str) } } } arr.sort((a,b) => b.length - a.length); if(!arr.length) return s[0] // for(let i = 0; i < arr.length; i++) { // if( arr[0].length === arr[i].length ) { // res.push(arr[i]) // } // } return arr[0] }; function isPalindrome(s) { return s === s.split('').reverse().join('') }

[@ТимофейБобыльков]

Что-то хорошее

[@frontendscience]

Благодарю! )

[@pavlo2846]

что-то хорошее