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.

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