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.
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