1=begin
 2two pointer:
 3* left
 4* right
 5
 6left moves ->
 7right moves <-
 8
 9* they move towards each other until they meet.
10* if all characters are the same while they move towards each
11other, then we have a palindrome.
12
13     l     r
14|b|a|n|a|n|a|
15
16
17|b|a|
18|b|a|n|
19|b|a|n|a|
20|b|a|n|a|n|
21|b|a|n|a|n|a|
22
23|a|n|
24|a|n|a|
25|a|n|a|n|
26|a|n|a|n|a|
27
28|n|a|
29|n|a|n|
30|n|a|n|a|
31
32|a|n|a|
33
34recursive solution
35base case:
36
37* s is empty
38
39if s[0] == s[-1]
40  run(s[1..-2])
41end
42=end
43
44def assert_equal(x, y)
45  return puts "PASS" if x == y
46  puts "FAIL: expected #{x}, got #{y}"
47end
48
49class Solution
50  def self.palindrome?(string)
51    return false if string.nil? || string.empty?
52
53    string == string.reverse
54  end
55
56  def self.run(string)
57    max = ""
58    for l in (0..string.size)
59      for r in (l+1..string.size)
60        candidate = string[l..r]
61        if palindrome?(candidate) && candidate.size > max.size
62          max = candidate
63        end
64      end
65    end
66    max
67  end
68end
69
70assert_equal 'anana', Solution.run('banana')
71assert_equal 'illi', Solution.run('million')
72assert_equal 'racecar', Solution.run('tracecars')
73assert_equal 'tacocat', Solution.run('loltacocatmom')