Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
*Substring Optimisation solution in Clear category for Long Non Repeat by JimmyCarlos
from copy import copy
# There are two methods here, one which is optimised and one which is not.
# The optimised one will be faster if s was very long.
def non_repeat(s):
# Choose which method to use.
useOptimisedMethod = True
if useOptimisedMethod: return non_repeat_optimised(s)
else: return non_repeat_unoptimised(s)
def non_repeat_unoptimised(s) -> str:
def is_nonRepeatingString(s) -> bool:
"""Tests if a string contains no repeating letters."""
return len(s) == len(set(s))
maxGroup = ""
# Iterate through all substrings by looking at all positions
# for Left hand side and Right hand side.
for L in range(len(s)+1):
for R in range(L+1,len(s)+1):
newString = s[L:R]
# Test if new string is valid and if longer.
if is_nonRepeatingString(newString) and len(newString) > len(maxGroup):
maxGroup = newString
return maxGroup
def non_repeat_optimised(s) -> str:
# Basic method:
# Represent all strings as dicts of letters -> letter frequencies,
# eg. "aaabb" -> {"a":3,"b":2,"c":0}
# To make things easier to use, we will use 1-based indexing.
# We will do this by anchoring s, eg. "nke" -> "*nke"
s = "*" + s
def is_nonRepeatingDict(d) -> bool:
"""Tests if a dict contains no repeating letters."""
return all(count <= 1 for count in d.values())
def remove_singleFrequencyDict(d,c) -> dict:
"""Removes a single count of the key c from the values of a dict."""
d[c] -= 1
return d
# We will first go through the whole string, updating the dict as necessary,
# and storing all stages of the dict in a list.
# We will also keep track of the best string we have found in a str variable.
dictsList = []
leftIndex,rightIndex = 1,0
bestString = ""
currentDict = {c:0 for c in "abcdefghijklmnopqrstuvwxyz"} # eg. {"a":-,"b":-,"c":0...}
dictsList.append(copy(currentDict))
for rightIndex in range(1,len(s[1:])+1):
# As we extend the range, find which letter is to be added
newChar = s[rightIndex]
# Add that letter into the dict representing the current string.
currentDict[newChar] += 1
# Check if the dict representing the string is allowed according to this question.
if is_nonRepeatingDict(currentDict): bestString = s[leftIndex:rightIndex+1]
# Store the current state of the dict represting the string
dictsList.append(copy(currentDict))
# Now we will move the leftIndex one step to the right, and find new dicts.
# However, this is easier than you think because we have stored the strings as dicts...
# ...all we need to do is remove the missingLetter from all the dicts!
# eg. suppose s = "ababb", dicts = [{a:0,b:0},{a:1,b:0},{a:1,b:1},{a:2,b:1},{a:2,b:2},{a:2,b:3}]
# If we now move to starting at the second letter, all we are losing is an a, so I just have to take away 1 from a!
for leftIndex in range(2,len(s[1:])+1):
charLost = s[leftIndex-1]
dictsList = [remove_singleFrequencyDict(d,charLost) for d in dictsList]
for rightIndex in range(leftIndex,len(s[1:])+1):
currentDict = dictsList[rightIndex]
if (is_nonRepeatingDict(currentDict) and
rightIndex-leftIndex+1 > len(bestString)):
bestString = s[leftIndex:rightIndex+1]
return bestString
Aug. 16, 2018
