Leetcode: Longest substring without repeating characters

Question

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.

• ian: Do you mean this? leetcode.com/problems/…

Answer 1

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