Min Deletions for Identical Strings

🚀 Day 168 of My LeetCode Journey 🚀 583. Delete Operation for Two Strings 🫧 In this problem, we are given two strings and need to find the minimum number of deletions required to make both strings the same. ▪️ Since we are only allowed to delete characters, the idea is to keep the characters that are common in both strings and remove the rest. ▪️ So first, I found the LCS between the two strings. The LCS represents the longest sequence of characters that appears in both strings in the same order. ▪️ I used dynamic programming to build a table where dp[i][j] stores the length of the LCS for the first i characters of word1 and the first j characters of word 2. ▪️ If the characters at the current positions match, we extend the subsequence by adding 1 to the previous result. ▪️ If they do not match, we take the maximum result from the previous possibilities. ▪️ After filling the table, we get the length of the LCS. ▪️ Finally, the minimum deletions needed are: (length of word1 − LCS) + (length of word2 − LCS) ▪️ This works because we keep the common characters and delete everything else from both strings. #LeetCode #DynamicProgramming #Strings #Python #CodingJourney #Day168 🔥

  • text

To view or add a comment, sign in

Explore content categories