Skip to content

Instantly share code, notes, and snippets.

@trainoasis
Created July 12, 2021 10:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save trainoasis/a5580e999a38bb14360bff01905b1fa5 to your computer and use it in GitHub Desktop.
Save trainoasis/a5580e999a38bb14360bff01905b1fa5 to your computer and use it in GitHub Desktop.
Largest distinct substring
def all_unique(s):
d = set()
for c in s:
if c in d:
return False
else:
d.add(c)
return True
def find_largest_distinct_substring(s):
n = len(s)
while n>0:
for i in range(len(s)-n+1):
substring = s[i:i+n]
if all_unique(substring):
return substring
n-=1
raise
print(find_largest_distinct_substring("abcbda"))
print(find_largest_distinct_substring("abca"))
print(find_largest_distinct_substring("bbbb"))
print(find_largest_distinct_substring("bbacbbc"))
print(find_largest_distinct_substring("abdefgabef"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment