# Ruby Solution - Bit Operation

• The crux of this problem is to solve

where the two words do not share common letters

As the word only contains `a-z`, we can use 26 bits to represent the letters each word consists of. For example, we can turn word `hello` into an integer whose binary form is

``````zyxwvutsrqponmlkjihgfedcba
00000000000100100010010000 # => 18576
``````

To check whether two words share common letters, we can use `&` bit operation in an efficient way.

In addition, to avoid TLE we need to

1. Pre-process each word to get its binary form, instead of calculating it on the run.
2. Sort the words by length, then pruning the small product. This is crucial for a Ruby script to pass this problem.
``````  def max_product(words)
words = words.sort_by(&:length).reverse

# 1. Pre-process each word into binary forms
bins = words.map do |word|
word.chars.reduce(0){|val, ch| val |= 1 << (ch.ord - 'a'.ord) }
end

max = 0
words.each_with_index do |a, i|
# 2. It'll be TLE without this pruning
next if a.length * a.length <= max

words[i+1..-1].each_with_index do |b, j|
next if (bins[i] & bins[i+1+j]).nonzero?

max = [ max, a.length * b.length ].max
end
end

max
end
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.