Find All Palindromes

excerpt: Solution for one of the common string interview questions. tags: expand-to-the-left expand-to-the-right value-comparison pairwise-comparison

Given a string find all non-single letter substrings that are palindromes.

For each letter in the input string, expand to the left and right. Check for even and odd length palindromes during expansion. Move to the next letter if a palindrome does not exist.

Expand one character to the left and right and compare them. If both are equal, print out the palindrome substring.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def find_palindromes_in_sub_string(input, j, k)
  while (j >= 0 && k < input.size)
    if (input[j] != input[k])
      break
    end

    puts (input[j..k])

    j -= 1
    k += 1
  end
end

def find_all_palindrome_substrings(input)
  for i in (0..input.size - 1)
    find_palindromes_in_sub_string(input, i - 1, i + 1)
    find_palindromes_in_sub_string(input, i, i + 1)
  end
end

p find_all_palindrome_substrings('aabbbaacc')