Longest Substring Without Repeating Characters ruby solution

longest_substring_without_repeating_character.rb

#Author: Shubham Mishra
#I/O: puts length_of_longest_substring("abcabcbb")
#O/P: 3


#Solution 1: Time optimised solution
def length_of_longest_substring(s)
    i, j = 0, 0
    sub_s = s[0]
    max = 0
    l = s.length
    while i < l do
        while (j+1) < l && !(sub_s.include? (s[j+1])) do
            sub_s << s[j+1]
            j = j + 1
        end
        max = [max, (j-i+1)].max
        i = i + 1
        sub_s = sub_s[1..]
    end
    max
end



#Solution 2: Memory optimised solution:
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    i, j = 0, 0
    sub_s = s[0]
    max = 0
    l = s.length
    while i < l do
        while (j+1) < l && !(sub_s.include? (s[j+1])) do
            sub_s << s[j+1]
            j = j + 1
        end
        max = [max, (j-i+1)].max
        if (j+1) < l
            s_i = sub_s.index((s[j+1])) + 1
            i = i + s_i
            sub_s = s_i < sub_s.length ? sub_s[s_i..] : ""
        else
            i = i + 1
            sub_s = sub_s[1..]
        end
    end
    max
end


#Solution 3:
def substrings_longest_first(str)
  return 0 if str == ''
  l = str.length
  max = 1
  (0...l).each do |i|
    (i...l).each do |j| 
      sub_s = str[i..(l - j)]
      next if sub_s.length <= max
      if sub_s.length == sub_s.split('').uniq.count && max < sub_s.length
        max = sub_s.length
      end
    end
  end
  max
end

#Below length_of_longest_substring is same as initial solution1
def length_of_longest_substring(s)
    i, j = 0, 0
    sub_s = s[0]
    max = 0
    l = s.length
    while i < l do
        while (j+1) < l && !(sub_s.include? (s[j+1])) do
            sub_s << s[j+1]
            j = j + 1
        end
        max = [max, (j-i+1)].max
        i = i + 1
        sub_s = sub_s[1..]
    end
    max
end


################ Whille executing in irb:

require 'benchmark'

# I/P (substrings_longest_first): 

time = Benchmark.measure do
  puts substrings_longest_first('abcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbb')
end

puts "Execution time: #{time.real} seconds"


# O/P:
6
Execution time: 0.05280399974435568 seconds



# I/P (length_of_longest_substring): 

time_2 = Benchmark.measure do
  puts length_of_longest_substring('abcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbbabcabcbbabcdefabcbbabcabcbb')
end

puts "Execution time: #{time_2.real} seconds"


# O/P:
6
Execution time: 0.0004000002518296242 seconds