Leetcode: Longest substring without repeating characters

Posted on

Problem

I saw the editorial solutions for this problem, but they are written in an unfamiliar language. I’d like to post my code, which worked, and understand the timing of my solution. I don’t understand how to judge Big-O time yet.

``````def length_of_longest_substring(s)

longest_sub,current_sub = "",""
s.each_char do |c|
if current_sub.include?(c)
longest_sub = current_sub if current_sub.length > longest_sub.length
current_sub=current_sub[current_sub.index(c)+1..-1]+c
else
current_sub+=c
end
end
longest_sub = current_sub if current_sub.length > longest_sub.length
longest_sub.length
end
``````

I assume that since I’m creating strings, my space complexity suffers somewhat. I’m not really sure how I would speed things up with time.

Solution

You have exploited the space complexity.

``````def findLongestSubstring(inputString)
hashMap = Hash.new
longestSubstringLength = 0
jIndex = 0
iIndex = 0
while(jIndex < inputString.length)
if(hashMap[inputString[jIndex]])
iIndex = [iIndex, hashMap[inputString[jIndex]]].max
end
longestSubstringLength = [longestSubstringLength, jIndex-iIndex+1].max
hashMap[inputString[jIndex]] = jIndex + 1
jIndex = jIndex + 1
end
longestSubstringLength
end
``````

This method makes use of HashMap which works efficiently in terms of complexity. Searching the element in HashMap works in O(1) and same goes for insertion. This way you can reduce the complexity of your program