В „това предизвикателство LeetCode“ от нас се иска да намерим дължината на най-дългия низ от знаци в предоставен низ, който не съдържа повтарящи се знаци. С други думи, в низа hello най-дългият подниз без повтарящи се знаци е hel (с дължина 3).

Основният метод за решаване на този проблем е с „движещ се прозорец“ и всички подходи по-долу използват някаква форма на това.

Решение #1: Двойна линия с набор

Това беше първият ми и най-малко сложен метод. В него преминаваме веднъж през всички символи в предоставения низ и след това за всеки един преминаваме през останалите символи, като добавяме всеки един в набор, докато намерим повтарящ се знак. В този момент проверяваме дали това е най-дългият низ, намерен досега, и съхраняваме дължината му, ако е така. Това се повтаря до края на низа, докато не намерим най-дългия подниз.

Решение #2: Масив

Това решение е подобно на горното, но вместо това използва масив за съхраняване на текущия низ, което има предимството да бъде подредено и да има функционалността splice и indexOf, която прави това решение особено лесно за окото и премахва необходимостта от вложени цикъл.

Решение #3: Карта

Потребителят на LeetCode nilath публикува това страхотно решение с помощта на карта, която коригирах, за да подобря четливостта. Той използва концепцията за движещ се прозорец, но използва Карти за светкавично бързо търсене. Интересното е, че тъй като картата е двойка ключ-стойност, можем да използваме буквата като ключ и позицията, в която се намира в низа, като стойност:

Решение #4: Задайте

Това решение е вдъхновено от „решението Java на jeantimex“ и се основава на концепцията за карта, но леко опростява нещата, за да използва Set вместо това. Това има предимството да намали сложността на кода, но вероятно вреди на четливостта:

Сравняване на решенията

Всички подходи (с изключение на двойния цикъл) са с подобна производителност и варират между тестовете достатъчно, за да бъдат незначителни:

Интересното обаче е, че процесорът на LeetCode е толкова оптимизиран за работа с масиви, че ако започнете всички тези подходи, като първо конвертирате низа в масив (използвайки string.split('')), ще видите подобрения в производителността навсякъде.