The length of the longest substring that needs to be removed to make one string equal to another string

In this article, we will discuss the problem of finding the length of the longest substring that needs to be removed to make one string equal to another. We will first understand the problem statement and then explore simple and efficient ways to solve the problem, along with their respective algorithmic and time complexities. Finally, we will implement the solution in C.

Problem Statement

Given two strings A and B, determine the length of the longest substring that needs to be deleted from string A so that it is equal to string B.

Naive method

The simplest way is to generate all possible substrings of string A, remove them one by one, and then check whether the resulting string is equal to string B. If it is, we store the length of the removed substring. Finally, we will return the maximum length among all removed substrings.

Algorithm (simple)

• Initialize maxLength to 0.

• Generate all possible substrings of string A

• For each substring, remove it from string A and check whether the resulting string is equal to string B.

• If yes, update maxLength to the maximum value between maxLength and the length of the deleted substring.

• Return the maximum length.

C code (plain)

Example

#include <iostream>
#include <string>
#include <algorithm>

int longestSubstringToDelete(std::string A, std::string B) {
   int maxLength = 0;
   
   for (int i = 0; i < A.length(); i++) {
      for (int j = i; j < A.length(); j++) {
         std::string temp = A;
         temp.erase(i, j - i + 1);
   
         if (temp == B) {
            maxLength = std::max(maxLength, j - i + 1);
         }
      }
   }
   
   return maxLength;
}

int main() {
   std::string A = "abcde";
   std::string B = "acde";
   
   std::cout << "Length of longest substring to be deleted: " << longestSubstringToDelete(A, B) << std::endl;
   
   return 0;
}

Output

Length of longest substring to be deleted: 1

Time complexity (naive) - O(n^3), where n is the length of string A.

Efficient method

An effective way to solve this problem is to find the longest common subsequence (LCS) of two strings. The length of the longest substring that needs to be deleted in string A so that it is equal to string B is the difference between the length of string A and the length of LCS.

Algorithm (efficient)

• Find the longest common subsequence (LCS) of string A and string B.

• Returns the difference between the length of string A and the length of LCS.

C code (efficient)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int longestCommonSubsequence(std::string A, std::string B) {
   int m = A.length();
   int n = B.length();
   std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
   
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (A[i - 1] == B[j - 1]) {
            
            dp[i][j] = 1 + dp[i - 1][j - 1];
         } else {
            dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
         }
      }
   }
   return dp[m][n];
}

int longestSubstringToDelete(std::string A, std::string B) {
   int lcsLength = longestCommonSubsequence(A, B);
   return A.length() - lcsLength;
}

int main() {
   std::string A = "abcde";
   std::string B = "acde";
   std::cout << "Length of longest substring to be deleted: " << longestSubstringToDelete(A, B) << std::endl;
   
   return 0;
}

Output

Length of longest substring to be deleted: 1

Time complexity (efficient) - O(m * n), where m is the length of string A and n is the length of string B.

in conclusion

In this article, we explore the problem of finding the length of the longest substring that needs to be removed to make one string equal to another. We discuss simple yet efficient methods for solving this problem, along with their algorithmic and time complexity. Efficient methods exploit the longest common subsequence concept and achieve significant improvements in time complexity compared to naive methods.

The above is the detailed content of The length of the longest substring that needs to be removed to make one string equal to another string. For more information, please follow other related articles on the PHP Chinese website!