Ruby - Find the longest non-repeating substring in any given string-CodePudding

I am working on an assignment where I have to take user input of a string and search through it to find the longest non-repeating string in it. So for example:

If the string is:

"abcabcabcdef"

My output needs to be:

"abcdef is the longest substring at the value of 6 characters"

Here is my poorly made code:

class Homework_4

  puts "Enter any string of alphabetical characters: "
  user_input = gets
  longest_str = 0
  empty_string = ""
  map = {}
  i = 0
  j = 0

  def long_substr()
    while j < str_len
      if map.key?(user_input[j])
        i = [map[user_input[j]], i].max
      end
      longest_str = [longest_str, j - i   1].max
      map[user_input[j]] = j   1
      j  = 1
    end
    longest_str
  end

  long_substr(user_input)
end

I have been working on this for over 6 hours today and I just can't figure it out. It seems like the internet has many ways to do it. Almost all of them confuse me greatly and don't really explain what they're doing. I don't understand the syntax they use or any of the variables or conditions.

All I understand is that I need to create two indicators that go through the inputted string searching for a non-repeating substring (sliding window method). I don't understand how to create them, what to make them do or even how to make them find and build the longest substring. It is very confusing to try and read the code that is full of random letters, symbols, and conditions. I'm sure my code is all sorts of messed up but any help or tips that could point me in the right direction would be greatly appreciated!

CodePudding user response：

def uniq?(s)
  # All letters of s uniq?
  return s.chars.uniq == s.chars
end

def subs(s)
  # Return all substrings in s.
  (0..s.length).inject([]){|ai,i|
    (i..s.length - i).inject(ai){|aj,j|
      aj << s[i,j]
    }
  }.uniq
end

def longest_usub(s)
  # Return first longest substring of s.
  substrings(s).inject{|res, s| (uniq?(s) and s.length > res.length) ? s : res}
end

ruby's inject is actually a reduce function, where inject(optional_start_value){<lambda expression>} - and the lambda expression is similar to Python's lambda x, y: <return expression using x and y> just that lambda expressions are strangely written in Ruby as {|x, y| <return expression using x and y>}.

Python's range(i, y) is Ruby's i..y.

Python's slicing s[i:j] is in Ruby s[i..j] or s[i,j].

<< means add to end of the array.

Second solution (inspired by @Rajagopalan's answer)

def usub(s)
  # Return first chunk of uniq substring in s
  arr = []
  s.chars do |char|
    break if arr.include? char
    arr << char
  end
  arr.join
end

def usubs(s)
  # Return each position's usub() in s
  (0..s.length).to_a.map{|i| usub(s[i,s.length])}
end
      
def longest_usub(s)
  # return for each position longest uniq subseqs
  usubs(s).max_by(&:length)
# or shorter:

def usub(s)
  s.chars.inject{|res, char| if res.include? char return res else res << char}
end
end

then you can do:

longest_usub("abcabcabcdef")
## "abcdef"

CodePudding user response：

A string is said to be repeating if it contains a substring s of one or one more characters that is followed by the same substring s. A string is non-repeating if it is not repeating.

A string is seen to be repeating if and only if it matches the regular expression

R = /([a-z] )\1/

Demo

The regular expression reads, "match one or more letters that are saved to capture group one, then match the content of capture group 1".

For convenience we can construct a simple helper method.

def nonrepeating?(str)
  !str.match? R
end

We will now determine if the entire string is non-repeating. If it is we return that string and we are finished. If it is repeating we examine the 2 substrings of length n-1, where n is the length of the string. If one is found to be non-repeating it is returned and we are finished; else we examine the 3 substrings of length n-2, and so on.

We can do that with the following method.

def longest(str)
  slen = str.size
  slen.downto(1) do |n|
    0.upto(slen-n) do |i|
      s = str[i,n]
      return s if nonrepeating?(s)
    end
  end
end

longest("dabcabcdef")
  #=> "bcabcdef"

CodePudding user response：

a = "abcabcabcdef"
arr = []
words = []
b=a
a.length.times do
  b.chars.each do |char|
    break if arr.include? char
    arr << char
  end
  words << arr.join
  arr.clear
  b=b.chars.drop(1).join
end

p words.map(&:chars).max_by(&:length).join

Output

"abcdef"