Поиск самой длинной подстроки без дубликатов - Помощь по оптимизации кода [Ruby]

Question

Итак, я пытался решить Leetcode Question , "По заданной строке найдите длину самой длинной подстроки без повторяющихся символов."

Например

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

В настоящее время я оптимизировал свой алгоритм, чтобы выяснить, является ли подстрока уникальной с помощью хеш-таблицы.Однако мой код все еще выполняется во время выполнения O (n ^ 2), и в результате превышается ограничение по времени при отправке.

Что я пытаюсь сделать, это, по сути, пройти каждую возможную подстроку и проверить, имеет ли оналюбые повторяющиеся значения.Я настолько эффективен, насколько это возможно, когда дело доходит до метода грубой силы?Я знаю, что есть другие методы, такие как метод скользящего окна, но я пытаюсь сначала использовать метод грубой силы.

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    max_length = 0
    max_string = ""
    n = s.length
    for i in (0..n-1)
        for j in (i..n-1)
            substring = s[i..j]
            #puts substring
            if unique(substring)
                if substring.length > max_length
                    max_length = substring.length
                    max_string = substring
                end
            end
        end
    end
    return max_length
end

def unique(string)
    hash = Hash.new(false)
    array = string.split('')
    array.each do |char|
        if hash[char] == true
            return false
        else
            hash[char] = true
        end
    end
    return true
end

Answer 1

Подход

Вот способ сделать это с помощью хэша, который отображает символы в индексы.Для строки s предположим, что символы в подстроке s[j..j+n-1] являются уникальными, и поэтому подстрока является кандидатом на самую длинную уникальную подстроку.Поэтому следующим элементом является e = s[j+n] Мы хотим определить, включает ли s[j..j+n-1] e.Если этого не произойдет, мы можем добавить e к подстроке, сохранив ее уникальность.

Если s[j..j+n-1] включает e, мы определяем, будет ли n (размер подстроки) больше, чемдлина ранее известной подстроки и обновите наши записи, если это так.Чтобы определить, включает ли s[j..j+n-1] e, мы могли бы выполнить линейный поиск подстроки, но быстрее поддерживать хеш c_to_i, чьи пары ключ-значение s[i]=>i, i = j..j_n-1.То есть c_to_i сопоставляет символы в подстроке с их индексами в полной строке s.Таким образом, мы можем просто оценить c_to_i.key?(e), чтобы увидеть, содержит ли подстрока e.Если подстрока включает e, мы используем c_to_i, чтобы определить ее индекс в s и добавляем один: j = c_to_i[e] + 1.Поэтому новая подстрока имеет значение s[j..j+n-1] с новым значением j.Обратите внимание, что на этом шаге можно пропустить несколько символов s.

Независимо от того, содержала ли подстрока e, теперь мы должны добавить e к (возможно обновленной) подстроке, чтобы онастановится s[j..j+n].

Код

def longest_no_repeats(str)
  c_to_i = {}
  longest = { length: 0, end: nil }
  str.each_char.with_index do |c,i|
    j = c_to_i[c]
    if j
      longest = { length: c_to_i.size, end: i-1 } if
        c_to_i.size > longest[:length]
      c_to_i.reject! { |_,k| k <= j }
    end
    c_to_i[c] = i
  end
  c_to_i.size > longest[:length] ? { length: c_to_i.size, end: str.size-1 } :
    longest
end

Пример

a = ('a'..'z').to_a
  #=> ["a", "b",..., "z"]

str = 60.times.map { a.sample }.join
  #=> "ekgdaxxzlwbxixhlfbpziswcoelplhobivoygmupdaexssbuuawxmhprkfms"

longest = longest_no_repeats(str)
  #=> {:length=>14, :end=>44} 
str[0..longest[:end]]
  #=> "ekgdaxxzlwbxixhlfbpziswcoelplhobivoygmupdaexs" 
str[longest[:end]-longest[:length]+1,longest[:length]]
  #=>                                "bivoygmupdaexs" 

Эффективность

Вот сравнительное сравнение с кодом @ mechnicov:

require 'benchmark/ips'

a = ('a'..'z').to_a
arr = 50.times.map { 1000.times.map { a.sample }.join }

Benchmark.ips do |x|
  x.report("mechnicov") { arr.sum { |s| max_non_repeated(s)[:length]   } }
  x.report("cary")      { arr.sum { |s| longest_no_repeats(s)[:length] } }
  x.compare!
end

отображает:

Comparison:
            cary:       35.8 i/s
       mechnicov:        0.0 i/s - 1198.21x  slower

Answer 2

Из вашей ссылки :

Ввод: "pwwkew"

Ввод: 3

Объяснение: Ответ "wke", длиной 3.

Это означает, что вам нужна первая неповторяющаяся подстрока.

Я предлагаю вот такой метод

def max_non_repeated(string)
  max_string = string.
                 each_char.
                 map.with_index { |_, i| string[i..].split('') }.
                 map do |v|
                   ary = []
                   v.each { |l| ary << l if ary.size == ary.uniq.size }
                   ary.uniq.join
                 end.
                 max

  {
    string: max_string,
    length: max_string.length
  }
end

max_non_repeated('pwwkew')[:string] #=> "wke"
max_non_repeated('pwwkew')[:length] #=> 3

В Ruby <2.6 используйте <code>[i..-1] вместо [i..]