Longest substrings without repeating characters: Difference between revisions

=={{header|Phix}}==

Single pass, maintains a table of seen characters and a start position.<br>

If the current character occurs in start..i we trim left until cleared, otherwise/then we add any longer/equal len start..i to the result set.<br>

Should be exponentially faster than collecting all possible substrings and then eliminating those with duplicate characters or too short.<br>

It will however collect duplicates before weeding them out at the end.

<!--<lang Phix>(phixonline)-->

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>

<span style="color: #000080;font-style:italic;">--

-- s can be a normal 8-bit ansi string or a

-- 32-bit unicode sequence from eg utf8_to_utf32().

-- it will not complain if given utf-8, but it may

-- chop up multi-byte characters inappropriately.

-- s must not contain any 0 or non-integer elements.

--</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>

<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">256</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (for ansi)</span>

<span style="color: #004080;">integer</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>

<span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>

<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>

<span style="color: #004080;">integer</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (deliberate typecheck)</span>

<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">found</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (for unicode)</span>

<span style="color: #000000;">found</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">si</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">found</span><span style="color: #0000FF;">))</span>

<span style="color: #008080;">elsif</span> <span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">si</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>

<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>

<span style="color: #004080;">integer</span> <span style="color: #000000;">ss</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">start</span><span style="color: #0000FF;">]</span>

<span style="color: #000000;">start</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>

<span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ss</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>

<span style="color: #008080;">if</span> <span style="color: #000000;">ss</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>

<span style="color: #000080;font-style:italic;">-- aside: we will not have found anything

-- longer, but may have trimmed 1 added 1

-- and therefore still be === maxlen.</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">si</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>

<span style="color: #004080;">integer</span> <span style="color: #000000;">newlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">start</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>

<span style="color: #008080;">if</span> <span style="color: #000000;">newlen</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span>

<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>

<span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newlen</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">if</span> <span style="color: #000000;">newlen</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span>

<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">start</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"STABLE"</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"xyzyabcybdfd"</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"xyzyab"</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"zzzzz"</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"a"</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>

<!--</lang>-->

{{out}}

<pre>

{"zyabc","cybdf"}

{"zyab"}

{"z"}

{"a"}

{}

</pre>

A quick test on unixdict.txt yielded the same results as Raku.