Longest substrings without repeating characters: Difference between revisions

{{trans|Python: Some optimisation}}

 

V max_subs = [s[0.<1]] * 0

V mx = 0

 

V arr = [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]

 

{{out}}

 

=={{header|Action!}}==

BYTE ARRAY tab(256)

BYTE i

Test("thisisastringtest")

Test("")

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_substrings_without_repeating_characters.png Screenshot from Atari 8-bit computer]

 

=={{header|Ada}}==

 

procedure Longest_Substring is

Test ("thisisastringtest");

Test ("zzzzz");

{{out}}

<pre>

 

=={{header|AutoHotkey}}==

found := [], result := [], maxL := 0

if (StrLen(str) = 1)

result[str] := true

return result

(

xyzyabcybdfd

}

MsgBox % output

{{out}}

<pre>xyzyabcybdfd > [cybdf, zyabc]

 

=={{header|BCPL}}==

 

// Fills up 'v' with words where w%0 is the start and w%1 is the end

example("a")

example("")

{{out}}

<pre>Original string: 'xyzyabcybdfd'

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

return 0;

{{out}}

<pre>Original string: "xyzyabcybdfd"

 

=={{header|C++}}==

#include <fstream>

#include <set>

test1();

test2("unixdict.txt");

 

{{out}}

=={{header|Factor}}==

{{works with|Factor|0.99 2021-06-02}}

 

: unique-substrings ( seq n -- newseq )

 

"Longest substrings without repeating characters:" print

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

 

function nrls( t as string ) as string

print ">";nrls("abcdefghijklmnopqrstuvwxyz");"<"

print ">";nrls("aaa aeiou uuu");"<"

{{out}}<pre>

>blishmentar<

=={{header|Go}}==

{{trans|Wren}}

 

import "fmt"

fmt.Printf("Length = %d\n\n", len(longest[0]))

}

 

{{out}}

 

=={{header|J}}==

c=. #y

while. ss=. c ]\ y do.

c=. c-1

end.

 

Examples:

 

zyabc

cybdf

ringtes

longnorep 'Thequickbrownfoxjumpsoverthelazydog'

 

This also works on sequences of numbers (though the character representation of the sequences of numbers may contain repeated characters, the represented numbers will not contain repetitions):

 

3 4 1 2 5 6

 

=={{header|jq}}==

{{works with|jq}}

'''Works with gojq, the Go implementation of jq'''

def alluniquehead:

length as $n

end)

| .ans;

'''Test Cases'''

"xyzyab",

"zzzzz",

""

| "\"\(.)\" => \"\(maximal_substring_with_distinct_characters)\""

{{out}}

<pre>

=={{header|Julia}}==

Works on any array, treating a character string as a character array.

len = length(arr)

if len > 1

println("\"$s\" => ", uarray)

end

<pre>

"xyzyabcybdfd" => ["zyabc", "cybdf"]

 

=={{header|Modula-2}}==

FROM InOut IMPORT WriteString, WriteLn;

FROM Strings IMPORT Length, Copy;

Example("a");

Example("");

{{out}}

<pre>Original string: xyzyabcybdfd

=={{header|Nim}}==

This version converts strings to sequences of runes.

 

type Runes = seq[Rune]

 

echo "\nLongest substrings in concatenated list of words from “unixdict.txt”: ",

 

{{out}}

=={{header|Perl}}==

Gets the same answer that raku does when run against unixdict.txt

 

use strict; # Longest_substrings_without_repeating_characters

length $+ >= $#sub and ++$sub[length $+]{$+} while s/.*(.)(.*\K\1.*)|(.+)//s;

printf "%20s -> %s\n", $string, join ' ', sort keys %{ pop @sub };

{{out}}

<pre>

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

It will however collect duplicates (when long enough) before weeding them out at the end.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</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>

{{out}}

<pre>

=={{header|Python}}==

The following algorithm works but is not terribly efficient for long strings.

substr = [s[x:y] for x in range(len(s)) for y in range(x+1, len(s) + 1)]

no_reps = []

for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "",

[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]:

 

{{out}}

===Python: Some optimisation===

The following algorithm only accrues the longest so far.

max_subs, mx = [], 0

for x in range(len(s)):

else:

max_subs, mx = [sub], y - x

 

{{out}}

 

Not going to bother handling arrays since an array is not a string, and the task description '''specifically''' says 'Given a string'.

 

sub longest ($string) {

 

# check a file

{{out}}

<pre>Original string: xyzyabcybdfd

 

=={{header|REXX}}==

parse arg $ /*obtain optional argument from the CL.*/

if $=='' | $=="," then $= 'xyzyabcybdfd' /*Not specified? Then use the default.*/

OKx: procedure; parse arg y; do r=1 for length(y)-1 /*look for duplicate chars.*/

if pos(substr(y, r, 1), y, r+1)>0 then return 0

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

see "working..." + nl

see "Longest substrings without repeating characters are:" + nl

 

see "done..." + nl

{{out}}

<pre>

 

=={{header|VBScript}}==

function nrls(byval s1)

dim i,x

test "aa"

test "abdefghij"

{{out}}

<pre>

=={{header|Vlang}}==

{{trans|go}}

n := s.len

if n == 0 {

println("Length = ${longest[0].len}\n")

}

{{out}}

<pre>Same as Wren entry</pre>

=={{header|Wren}}==

{{libheader|Wren-seq}}

 

var substrings = Fn.new { |s|

System.print(longest)

System.print("Length = %(longest[0].count)\n")

 

{{out}}