Longest substrings without repeating characters: Difference between revisions
Content added Content deleted
(Add Python) |
|||
| Line 58: | Line 58: | ||
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "", |
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "", |
||
[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]: |
[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]: |
||
print(f"{s} => {longest_substring(s)}") |
print(f"{s} => {longest_substring(s)}")</lang> |
||
</lang> |
|||
{{out}} |
{{out}} |
||
| Line 70: | Line 69: | ||
[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0] => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]</pre> |
[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0] => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]</pre> |
||
===Python: Some optimisation=== |
|||
The following algorithm only accrues the longest so far. |
|||
<lang python>def longest_substring2(s = "xyzyab"): |
|||
max_subs, mx = [], 0 |
|||
for x in range(len(s)): |
|||
for y in range(x+1, len(s) + 1): |
|||
sub = s[x:y] |
|||
if y - x >= mx and len(sub) == len(set(sub)): |
|||
if y - x == mx and sub not in max_subs: |
|||
max_subs.append(sub) |
|||
else: |
|||
max_subs, mx = [sub], y - x |
|||
return max_subs</lang> |
|||
{{out}} |
|||
It gives the same output as function <code>longest_substring()</code> above. |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||