Session 41: DP 3 on Strings

Original Session

Date: 13 Feb 2025

Topic: DP on Strings

Concept: Subsequence vs Substring.

Concept: Substring Always continuos.
“ara” is substring from “characters”.
“rct” is not a substring from “characters”.

Concept: Subsequence may or may not be continous as well.
But character need to follow the order.
substring is subset of subsequence.
“rct” and “ara” is subsequence from “characters”.

Programs

1. 1143. Longest Common Subsequence
   1. leetcode here
      1. When empty everything is zero.
      2. When matching, diagonal + 1.
      3. When not matching, max(left, up).

      

      public int longestCommonSubsequence(String text1, String text2) {
              
              int n = text1.length();
              int m = text2.length();
      
              int[][] dp = new int[n+1][m+1];
              for (int i = 1; i<=n; i++) {
      
                  for (int j = 1; j<=m; j++) {
      
                      if (text1.charAt(i-1) == text2.charAt(j-1)) {
                          dp[i][j] = 1 + dp[i-1][j-1]; 
                      } else {
                          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                      }
                  }
              }
              return dp[n][m];
        }

2. 718. Maximum Length of Repeated Subarray (substring)
   1. leetcode here
      1. When empty everything is zero.
      2. When matching, diagonal + 1.
      3. When not matching, zero.

      public int findLength(int[] nums1, int[] nums2) {
          
          int n = nums1.length;
          int m = nums2.length;
          int max = 0;
      
          int[][] dp = new int[n+1][m+1];
          for (int i = 1; i<=n; i++) {
      
              for (int j = 1; j<=m; j++) {
      
                  if (nums1[i-1] == nums2[j-1]) {
      
                      dp[i][j] = 1 + dp[i-1][j-1]; 
                      max = Math.max(max, dp[i][j]);
                  } else {
      
                      dp[i][j] = 0;
                  }
              }
          }
          return max;
      }

3. 516. Longest Palindromic Subsequence
   1. leetcode here

      public int longestPalindromeSubseq(String s) {
              
          String text1 = s;
          String text2 = new StringBuilder(s).reverse().toString();
          int n = text1.length();
          int m = text2.length();
      
          int[][] dp = new int[n+1][m+1];
          for (int i = 1; i<=n; i++) {
      
              for (int j = 1; j<=m; j++) {
      
                  if (text1.charAt(i-1) == text2.charAt(j-1)) {
                      dp[i][j] = 1 + dp[i-1][j-1]; 
                  } else {
                      dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                  }
              }
          }
          return dp[n][m];
      }

4. Shortest Common Supersequence
   1. GFG practice here
      1. m + n - LCSequence
      2. geek, eke = geeke

      int shortestCommonSupersequence(String s1, String s2) {
              // Your code here
              
              int n = s1.length();
              int m = s2.length();
              
              int[][] dp = new int[n+1][m+1];
              for (int i = 1; i<=n; i++) {
      
                  for (int j = 1; j<=m; j++) {
      
                      if (s1.charAt(i-1) == s2.charAt(j-1)) {
                          dp[i][j] = 1 + dp[i-1][j-1]; 
                      } else {
                          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                      }
                  }
              }
              return m + n - dp[n][m];
          }

5. Minimum number of deletions and insertions
   1. GFG practice here

      public int minOperations(String s1, String s2) {
              
              int n = s1.length();
              int m = s2.length();
              
              int[][] dp = new int[n+1][m+1];
              for (int i = 1; i<=n; i++) {
      
                  for (int j = 1; j<=m; j++) {
      
                      if (s1.charAt(i-1) == s2.charAt(j-1)) {
                          dp[i][j] = 1 + dp[i-1][j-1]; 
                      } else {
                          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                      }
                  }
              }
              return m - dp[n][m] + n - dp[n][m];
              
          }

6. 583. Delete Operation for Two Strings
   1. leetcode here

      public int minDistance(String word1, String word2) {
              
          int n = word1.length();
          int m = word2.length();
          
          int[][] dp = new int[n+1][m+1];
          for (int i = 1; i<=n; i++) {
      
              for (int j = 1; j<=m; j++) {
      
                  if (word1.charAt(i-1) == word2.charAt(j-1)) {
                      dp[i][j] = 1 + dp[i-1][j-1]; 
                  } else {
                      dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                  }
              }
          }
          return m - dp[n][m] + n - dp[n][m];
      }