HackerRank Challenge - Special Substrings

substring.rb

#!/bin/ruby
require 'pry-byebug'
require 'set'
# require 'trie'

# So this code works correctly, but it's horribly slow. Probably it needs a trie-based approach.

SPECIAL = {}

PREFIX = {}

PALINDROME = {}

SUB = {}

def propertyOfString(s,n)

  def prefix_strings(str)
    acc = ''
    PREFIX[str] ||= str.chars.map {|c| acc += c }
    # PREFIX[str] ||= Trie.new.add(str)
  end

  def palindrome?(str)
    # binding.pry
    i = str.length/2
    PALINDROME[str] ||= (0..i).none? { |e| str[e] != str[str.length - 1 - e] }
  end

  def all_substrs(s)
    l = s.length
    SUB[s] ||= (0..l).inject(Set.new){|ai,i|
      (1..l - i).inject(ai){|aj,j|
        aj << s[i,j]
      }
    }
    # m = []
    # (0..l).each do |i|
    #   (i+1..l).each do |j|
    #     m << s[i,j]
    #   end
    # end
    # m
  end

  def special_substr(str)
    SPECIAL[str] ||= all_substrs(str).select { |i| palindrome?(i) }
  end
  # binding.pry
  prefix_strings(s)
    .map { |i| special_substr(i) }
    .map { |i|  i.flat_map {|i| prefix_strings(i)}.uniq.length }
end

# n = gets.strip.to_i
# s = gets.strip
if (ENV['PROFILE'])
require 'ruby-prof'
[10,100,150].each do |n|
range = [*'a'..'z']
s = Array.new(n){ range.sample}.join
RubyProf.start
result = propertyOfString(s,n)
r = RubyProf.stop
printer = RubyProf::FlatPrinter.new(r)
printer.print(STDOUT)
end
else
n = 8
s = 'bccbbbbc'
result = propertyOfString(s,n)
print result.join("\n")
end