Longest Palindrome

Write a method that takes in a string of lowercase letters (no uppercase letters, no repeats). Consider the *substrings* of the string: consecutive sequences of letters contained inside the string.  Find the longest such string of letters that is a palindrome.

Note that the entire string may itself be a palindrome.

You may want to use Array’s ‘slice(start_index, length)’ method, which returns a substring of length ‘length’ starting at index ‘start_index’:

“abcd”.slice(1, 2) == “bc”
“abcd”.slice(1, 3) == “bcd”
“abcd”.slice(2, 1) == “c”
“abcd”.slice(2, 2) == “cd”

Screen Shot 2016-08-22 at 7.00.54 PM

Second time solving this, I annotated much more to clarify my thought process.

1. Write a method to check if a string is a palindrome to use in main method.

screen-shot-2016-09-20-at-11-22-52-pm

2. Build a list of potential substrings by slicing them out at different indices and lengths.

Example:

indices:  0 1 2 3 4 5 6 7 8
string:    a b c b d e f  f  e  =>  e f f e

idx = 0: a, ab, abc, abcb, abcbe, abcbdef, abcbdeff, abcbdeffe
idx = 1: b, bc, bcb, bcbd, bcbde, bcbdef, bcbdeff, bcbdeffe
idx = 2: c, cb, cbd, cbdef, cbdeff, cbdeffe
idx = 3: b, bd, bdef, bdeff, cbdeffe
idx = 4: d, de, def, deff, bdeffe
idx = 5: e, ef, eff, effe
idx = 6: f, ff, ffe
idx = 7: f, fe
idx = 8: e

3. Use previous ‘palindrome?’ method to check if each substring is a palindrome.

4. If it is a palindrome, compare its length to the previous palindrome and if
it’s greater, replace it as the longest palindrome.

screen-shot-2016-09-20-at-11-23-32-pm

Third time doing this, I realized I could set the default longest palindrome to an empty string instead of nil, and it should still work.

screen-shot-2016-11-07-at-1-45-45-pm

 

Advertisements
Longest Palindrome

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s