第15回オフラインリアルタイムどう書くの参考問題をRubyで解けてない

問題はこちらのリンクから。
http://qiita.com/Nabetani/items/0b56395d4c9e7c64b230

問題が文字列が長い場合(#20等)はまともな時間で解けないです。

def solve(q)
  max = 0
  (2**q.size).times{|i|
    w = ("%0#{q.size}b"%i).chars.zip(q.chars).select{|e| e[0]=='1'}
    max = w.size if w.size > max && w == w.reverse 
  }
  max
end

DATA.readlines.each do |line|
  no,q,a,s = line.chop.split(/\s+/)
  ans = solve(q)
  print no + "\t" + ans.to_s
  puts ans == a.to_i ? ' o' : ' x'
end
__END__
0   I_believe_you_can_solve 9   evo_n_ove
1   a   1   a
2   aa  2   aa
3   aaa 3   aaa