Code_Craft_can_form_palindrome.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPGCNxBZP09kOIjaCNMdC3T",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/walkerjian/DailyCode/blob/main/Code_Craft_can_form_palindrome.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Problem:\n",
        "Given a string which we can delete at most k, return whether you can make a palindrome.\n",
        "\n",
        "For example, given 'waterrfetawx' and a k of 2, you could delete f and x to get 'waterretaw'."
      ],
      "metadata": {
        "id": "A1pAAVRCb49i"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Solution:\n",
        "To solve this problem, we can use a dynamic programming approach. The idea is to check whether we can transform the given string into a palindrome by removing at most \\( k \\) characters. The key insight is to use a helper function that determines the minimum number of deletions required to turn a substring into a palindrome.\n",
        "\n",
        "Here's the plan:\n",
        "\n",
        "1. **Base Case:** If the string is already a palindrome or has a length of 0 or 1, we don't need to delete any characters.\n",
        "\n",
        "2. **Recursive Case:** We check two cases:\n",
        "   - If the first and last characters of the string are the same, we recursively check the substring excluding these two characters.\n",
        "   - If they are different, we need to consider removing one of them. We take the minimum number of deletions required when removing the first character or the last character and add 1 (since we are deleting one character).\n",
        "\n",
        "3. We compare the minimum number of deletions required to make the string a palindrome with \\( k \\). If it's less than or equal to \\( k \\), we return `True`, else `False`.\n"
      ],
      "metadata": {
        "id": "lSbK3AK0b_P0"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Implementation:\n"
      ],
      "metadata": {
        "id": "XqjyDZ6gcE_j"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8U4H15M-XcFT",
        "outputId": "309e32fe-195a-415b-892d-ce7c6ab03514"
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 1
        }
      ],
      "source": [
        "def can_form_palindrome(s, k):\n",
        "    # Helper function to find the minimum number of deletions required\n",
        "    # to make a substring a palindrome.\n",
        "    def min_deletions(i, j, memo):\n",
        "        if i >= j:\n",
        "            return 0\n",
        "        if (i, j) in memo:\n",
        "            return memo[(i, j)]\n",
        "\n",
        "        if s[i] == s[j]:\n",
        "            memo[(i, j)] = min_deletions(i + 1, j - 1, memo)\n",
        "        else:\n",
        "            # Either delete character at i or at j and take the minimum\n",
        "            memo[(i, j)] = 1 + min(min_deletions(i + 1, j, memo), min_deletions(i, j - 1, memo))\n",
        "\n",
        "        return memo[(i, j)]\n",
        "\n",
        "    memo = {}\n",
        "    return min_deletions(0, len(s) - 1, memo) <= k\n",
        "\n",
        "# Test the function with the provided example\n",
        "test_string = \"waterrfetawx\"\n",
        "k = 2\n",
        "can_form_palindrome(test_string, k)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "The function correctly determines that it is possible to transform the string \"waterrfetawx\" into a palindrome by deleting at most 2 characters. In this case, deleting 'f' and 'x' will yield the palindrome \"waterretaw\", as expected."
      ],
      "metadata": {
        "id": "K6kGU-NTcJIq"
      }
    }
  ]
}