{"id":1001,"date":"2025-08-26T16:36:39","date_gmt":"2025-08-26T11:06:39","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1001"},"modified":"2025-08-26T16:36:41","modified_gmt":"2025-08-26T11:06:41","slug":"delete-operation-for-two-strings","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/","title":{"rendered":"Delete Operation for Two Strings | Leetcode 583"},"content":{"rendered":"\n<p>You are given two strings <code>word1<\/code> and <code>word2<\/code>. In one operation, you can delete exactly one character from either string. Return the <strong>minimum number of deletions<\/strong> required so that the two strings become the same.<\/p>\n\n\n\n<p>Key idea: if <code>LCS(word1, word2)<\/code> is the length of their <strong>Longest Common Subsequence<\/strong>, then<br><strong>minimum deletions = len(word1) + len(word2) \u2212 2 \u00d7 LCS(word1, word2)<\/strong>.<br>Everything outside the LCS must be deleted from one side or the other.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/delete-operation-for-two-strings\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"word1 = &quot;sea&quot;, word2 = &quot;eat&quot;\nLCS = &quot;ea&quot; with length 2\nAnswer = 3 + 3 \u2212 2\u00d72 = 2\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #9CDCFE\">word1<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #CE9178\">&quot;sea&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word2<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #CE9178\">&quot;eat&quot;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #9CDCFE\">LCS<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #CE9178\">&quot;ea&quot;<\/span><span style=\"color: #D4D4D4\"> with length <\/span><span style=\"color: #B5CEA8\">2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #9CDCFE\">Answer<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\"> + <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\"> \u2212 <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">\u00d7<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #B5CEA8\">2<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p><strong>Example 2<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"word1 = &quot;leetcode&quot;, word2 = &quot;etco&quot;\nLCS length = 4\nAnswer = 8 + 4 \u2212 2\u00d74 = 4\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #9CDCFE\">word1<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #CE9178\">&quot;leetcode&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word2<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #CE9178\">&quot;etco&quot;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">LCS <\/span><span style=\"color: #9CDCFE\">length<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #B5CEA8\">4<\/span><\/span>\n<span class=\"line\"><span style=\"color: #9CDCFE\">Answer<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #B5CEA8\">8<\/span><span style=\"color: #D4D4D4\"> + <\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\"> \u2212 <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">\u00d7<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #B5CEA8\">4<\/span><\/span><\/code><\/pre><\/div>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-9f700a48-57b1-42b7-a47a-931feed726db\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Content:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#0-memoization\" style=\"\">Memoization<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#1-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#2-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#3-code-explanation\" style=\"\">Code explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#4-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#5-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#6-tabulation\" style=\"\">Tabulation<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#7-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#8-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#9-code-explanation\" style=\"\">Code explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#10-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#11-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#12-tabulation-space-optimize\" style=\"\">Tabulation (Space Optimize)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#13-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#14-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#15-code-explanation\" style=\"\">Code explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#16-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#17-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/delete-operation-for-two-strings\/#18-final-takeaway\" style=\"\">Final takeaway<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>Below are three solutions. We explain the problem only once at the top, then for each solution provide Intuition and Approach, Code Implementation, Code explanation, Time and Space Complexity, and a short Conclusion.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-memoization\">Memoization<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<p>Compute <strong>LCS<\/strong> using top down recursion with caching.<br>Let <code>solve(i, j)<\/code> be the LCS length of prefixes <code>word1[:i]<\/code> and <code>word2[:j]<\/code> using 1-based lengths:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If <code>i == 0<\/code> or <code>j == 0<\/code>, result is 0.<\/li>\n\n\n\n<li>If <code>word1[i-1] == word2[j-1]<\/code>, take <code>1 + solve(i-1, j-1)<\/code>.<\/li>\n\n\n\n<li>Else take <code>max(solve(i-1, j), solve(i, j-1))<\/code>.<\/li>\n<\/ul>\n\n\n\n<p>Finally compute deletions as <code>n + m \u2212 2 \u00d7 lcs<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, text1: str, text2: str, ind1: int, ind2: int, dp) -&gt; int:\n        if ind1 == 0 or ind2 == 0:\n            return 0\n        if dp[ind1][ind2] != -1:\n            return dp[ind1][ind2]\n        if text1[ind1 - 1] == text2[ind2 - 1]:\n            dp[ind1][ind2] = 1 + self.solve(text1, text2, ind1 - 1, ind2 - 1, dp)\n        else:\n            dp[ind1][ind2] = 0 + max(\n                self.solve(text1, text2, ind1 - 1, ind2, dp),\n                self.solve(text1, text2, ind1, ind2 - 1, dp)\n            )\n        return dp[ind1][ind2]\n\n    def minDistance(self, word1: str, word2: str) -&gt; int:\n        n = len(word1)\n        m = len(word2)\n        dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]\n        lcs = self.solve(word1, word2, n, m, dp)\n        return n + m - (2 * lcs)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">text1<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">text2<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ind1<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ind2<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">dp<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> ind1 == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> ind2 == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> dp[ind1][ind2] != -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[ind1][ind2]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> text1[ind1 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] == text2[ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            dp[ind1][ind2] = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(text1, text2, ind1 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, dp)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            dp[ind1][ind2] = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> + <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(text1, text2, ind1 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, ind2, dp),<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(text1, text2, ind1, ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, dp)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            )<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[ind1][ind2]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minDistance<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word1<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word2<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(word1)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(word2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        lcs = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(word1, word2, n, m, dp)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> n + m - (<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\"> * lcs)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code-explanation\">Code explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>dp[i][j]<\/code> caches LCS length for prefixes of lengths <code>i<\/code> and <code>j<\/code>.<\/li>\n\n\n\n<li>Matching characters extend the subsequence from the diagonal state.<\/li>\n\n\n\n<li>Otherwise, we try skipping one character from either string and take the maximum.<\/li>\n\n\n\n<li>After computing LCS, use the formula to get the minimum deletions.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Precise: states <code>n*m<\/code>, each computed once, time <strong>O(n*m)<\/strong>; DP table <strong>O(n*m)<\/strong> and recursion stack <strong>O(n + m)<\/strong>.<\/li>\n\n\n\n<li>Simplified: <strong>O(n*m)<\/strong> time, <strong>O(n*m)<\/strong> space.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Memoization converts exponential recursion into polynomial time and is simple to implement.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-tabulation\">Tabulation<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<p>Bottom up dynamic programming for <strong>LCS<\/strong>. Build a <code>(n+1) \u00d7 (m+1)<\/code> table where row 0 and column 0 are zeros, then apply the standard match or max transition. Answer is <code>n + m \u2212 2 \u00d7 dp[n][m]<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -&gt; int:\n        n = len(text1)\n        m = len(text2)\n        dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]\n        for ind2 in range(0, m + 1):\n            dp[0][ind2] = 0\n        for ind1 in range(0, n + 1):\n            dp[ind1][0] = 0\n        for ind1 in range(1, n + 1):\n            for ind2 in range(1, m + 1):\n                if text1[ind1 - 1] == text2[ind2 - 1]:\n                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]\n                else:\n                    dp[ind1][ind2] = 0 + max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])\n        return dp[n][m]\n\n    def minDistance(self, word1: str, word2: str) -&gt; int:\n        n = len(word1)\n        m = len(word2)\n        lcs = self.longestCommonSubsequence(word1, word2)\n        return n + m - (2 * lcs)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">longestCommonSubsequence<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">text1<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">text2<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(text1)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(text2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(m + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ind2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, m + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            dp[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][ind2] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ind1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            dp[ind1][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ind1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ind2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, m + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> text1[ind1 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] == text2[ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    dp[ind1][ind2] = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> + dp[ind1 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    dp[ind1][ind2] = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> + <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(dp[ind1 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][ind2], dp[ind1][ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[n][m]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minDistance<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word1<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word2<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(word1)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(word2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        lcs = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.longestCommonSubsequence(word1, word2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> n + m - (<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\"> * lcs)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-code-explanation\">Code explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Initialize base cases for empty prefixes.<\/li>\n\n\n\n<li>For each cell, extend on match or carry forward the best from top or left on mismatch.<\/li>\n\n\n\n<li>Use the LCS length in the deletion formula.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Precise: fill <code>n*m<\/code> cells in <strong>O(1)<\/strong> each, time <strong>O(n*m)<\/strong>; table <strong>O(n*m)<\/strong> space.<\/li>\n\n\n\n<li>Simplified: <strong>O(n*m)<\/strong> time, <strong>O(n*m)<\/strong> space.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Deterministic and stack safe. Also convenient if you later want to reconstruct the LCS.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"12-tabulation-space-optimize\">Tabulation (Space Optimize)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<p><code>dp[i][j]<\/code> depends only on the previous row and the current row\u2019s previous cell. Keep two 1D arrays to reduce space to linear.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -&gt; int:\n        n = len(text1)\n        m = len(text2)\n        prev = [0] * (m + 1)\n\n        for ind1 in range(1, n + 1):\n            cur = [0] * (m + 1)\n            for ind2 in range(1, m + 1):\n                if text1[ind1 - 1] == text2[ind2 - 1]:\n                    cur[ind2] = 1 + prev[ind2 - 1]\n                else:\n                    cur[ind2] = 0 + max(prev[ind2], cur[ind2 - 1])\n            prev = cur\n\n        return prev[m]\n\n    def minDistance(self, word1: str, word2: str) -&gt; int:\n        n = len(word1)\n        m = len(word2)\n        lcs = self.longestCommonSubsequence(word1, word2)\n        return n + m - (2 * lcs)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">longestCommonSubsequence<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">text1<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">text2<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(text1)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(text2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * (m + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ind1 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            cur = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * (m + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ind2 <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, m + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> text1[ind1 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] == text2[ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    cur[ind2] = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> + prev[ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    cur[ind2] = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> + <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(prev[ind2], cur[ind2 - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev = cur<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> prev[m]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minDistance<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word1<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">word2<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(word1)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(word2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        lcs = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.longestCommonSubsequence(word1, word2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> n + m - (<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\"> * lcs)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-code-explanation\">Code explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>prev[j]<\/code> holds the previous row\u2019s LCS values and <code>cur[j]<\/code> the current row\u2019s values.<\/li>\n\n\n\n<li>Update from <code>prev[j-1]<\/code>, <code>prev[j]<\/code>, and <code>cur[j-1]<\/code>.<\/li>\n\n\n\n<li>After each row, roll <code>cur<\/code> into <code>prev<\/code>.<\/li>\n\n\n\n<li>Compute deletions using the final LCS value.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"16-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Precise: still <strong>O(n*m)<\/strong> time; arrays of size <code>m+1<\/code> give <strong>O(m)<\/strong> extra space.<\/li>\n\n\n\n<li>Simplified: <strong>O(n*m)<\/strong> time, <strong>O(min(n, m))<\/strong> space if you iterate columns along the shorter string.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Same optimal time with significantly less memory, ideal when only the count of deletions is needed.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"18-final-takeaway\">Final takeaway<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The minimum deletions to make two strings equal equals the total length minus twice the LCS length.<\/li>\n\n\n\n<li>Memoization, tabulation, and space optimized tabulation all achieve <strong>O(n*m)<\/strong> time.<\/li>\n\n\n\n<li>Choose the space optimized method for large inputs and memory efficiency, or tabulation if you might reconstruct the LCS later.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are given two strings word1 and word2. In one operation, you can delete exactly one character from either string. Return the minimum number of deletions required so that the two strings become the same. Key idea: if LCS(word1, word2) is the length of their Longest Common Subsequence, thenminimum deletions = len(word1) + len(word2) \u2212<\/p>\n","protected":false},"author":1,"featured_media":1002,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ub_ctt_via":"","footnotes":""},"categories":[3,6],"tags":[42,19],"class_list":{"0":"post-1001","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-dynamic-programming-on-strings","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/delete-operation-for-two-strings-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1001","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=1001"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1001\/revisions"}],"predecessor-version":[{"id":1006,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1001\/revisions\/1006"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/1002"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=1001"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=1001"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=1001"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}