Skip to content

Instantly share code, notes, and snippets.

@aniruddha84
Last active May 7, 2016 18:07
Show Gist options
  • Save aniruddha84/f5b117cefd0195ee01fdf04f29f8b0be to your computer and use it in GitHub Desktop.
Save aniruddha84/f5b117cefd0195ee01fdf04f29f8b0be to your computer and use it in GitHub Desktop.
Longest non-repeating substring
def longest_nonrepeating_substring(str)
max_len = 0
look_up = {}
len = 0
last_repeating_index = 0 # indicates beginning of unique string
(0...str.size).each do |index|
if (p = look_up[str[index]]) # repeat char found at index
if p > last_repeating_index
len = index - p
last_repeating_index = p
else
len = index - last_repeating_index
end
else
len += 1
end
look_up[str[index]] = index
max_len = [max_len, len].max
end
max_len
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment