Find possible palindromes

realisation.rb

# https://www.careercup.com/page?pid=amazon-interview-questions&job=quality-assurance-engineer-interview-questions
# "aabcbcbdcc" you can remove and shuffle characters, find the maximum length of string which forms palindrome. 
# like "ccabdbacc"

cases = [
	'zmasa3asesa'
]

def test_my_realisation(cases)
	cases.each do |string|
		result = find_lengthiest_palindrome(string)
		test_results(string, result)
	end
end 

def test_results(input, output)
	raise "No palindromes returned from #{input}" unless output
	raise "#{output} not palindrome" unless output.palindrome?
	raise "#{output} is greater than #{input}" if output.size > input.size
	puts output
end

class String
	def palindrome?
		return false if self.size < 2
		self.reverse == self
	end
end

class Array
	def palindrome?
		return false if self.size < 2
		self.join.reverse == self.join
	end
end

def find_lengthiest_palindrome(string)
	letters = string.chars
	possible_variants = []

	found = false
	
	# the lengthiests
	puts 'Trying full length variants'
	return string if string.palindrome?
	permutations = letters.permutation
	puts "Scanning for #{permutations.size} variants"
	possible_variants << permutations.to_a
	found = possible_variants.flatten(1).find(&:palindrome?)
	if found
		puts "Found #{found}"
		return found.join
	end

	# decrease by letter until found
	letters_to_delete = 1
	iterations = letters.size
	puts "Removing #{letters_to_delete} letter until found"
	loop do
		break if iterations == 0
			other_variants = []
			cloned = letters.dup
			break if (cloned.size - letters_to_delete) < 2
			rmvd = ''
			_i = 0
			letters_to_delete.times do
				rmvd << cloned.delete_at(_i)
			end
			puts "Removed '#{rmvd}' letter index #{_i}"

			vars = cloned.permutation
			puts "Trying for #{vars.size} variants"
			other_variants << vars.to_a
			found = other_variants.flatten(1).find(&:palindrome?)
			return found.join if found
		puts "Increasing removed letters count"
		letters_to_delete += 1
		iterations -= 1
	end
	return found
end

test_my_realisation(cases)

task

https://www.careercup.com/page?pid=amazon-interview-questions&job=quality-assurance-engineer-interview-questions

"aabcbcbdcc" you can remove and shuffle characters, find the maximum length of string which forms palindrome. Like "ccabdbacc".