Finding_the_longest_palindrome.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finding the Longest palindrome Substring\n",
    "\n",
    "Jacob L. Fine\n",
    "\n",
    "June 13th, 2024\n",
    "\n",
    "A classic string-searching algorithm is to find the longest palindrome substring for a given string.\n",
    "\n",
    "We will implement a canonical approach, where we iterate through each position in the string. We use each iteration as a 'seed', and extend the seed substring by one character on either side during each iteration. After each iteration, we ask if our current palindrome is larger than the working largest pallidrome. We do so until the longest palindrome is found."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "longest palindrome:\n",
      "GGGAAAATATATATATATAAAAGGG\n"
     ]
    }
   ],
   "source": [
    "def find_longest_palindrome(s):\n",
    "    if not s:\n",
    "        return ''\n",
    "\n",
    "    longest_palindrome = ''  # placeholder for the longest palindrome\n",
    "\n",
    "    # Go through all the indices of the palindrome\n",
    "    for i in range(len(s)):\n",
    "\n",
    "        # first considers palindromes of odd-length\n",
    "        left_pos, right_pos = i, i  # each i will be the seed of the current iteration of the search\n",
    "        while left_pos >= 0 and right_pos < len(s) and s[left_pos] == s[right_pos]:  # this condition ensures that extended substring is a palindrome\n",
    "            if right_pos - left_pos + 1 > len(longest_palindrome):  # we compare the length to the current longest palindrome\n",
    "                longest_palindrome = s[left_pos:right_pos+1]  # we then slice the string according to the longest palindrome\n",
    "            left_pos -= 1  # this grows the left and right sides of the substring evenly on each side to consider the next larger possible case\n",
    "            right_pos += 1\n",
    "\n",
    "        # now, we repeat the above but considering palindromes of even-length, so the initial middle portion will be 2 characters long\n",
    "        left_pos, right_pos = i, i + 1\n",
    "        while left_pos >= 0 and right_pos < len(s) and s[left_pos] == s[right_pos]:\n",
    "            if right_pos - left_pos + 1 > len(longest_palindrome):\n",
    "                longest_palindrome = s[left_pos:right_pos+1]\n",
    "            left_pos -= 1\n",
    "            right_pos += 1\n",
    "\n",
    "    return longest_palindrome\n",
    "\n",
    "s = 'GACGCAGCGCACGGGAAAATATATATATATAAAAGGGTACGACAGC'  # this can be a string of DNA\n",
    "\n",
    "longest_palindrome = find_longest_palindrome(s)\n",
    "print('longest palindrome:')\n",
    "print(longest_palindrome)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}