Leetcode daily

Hi,

I wanted to you my idea for the solution for LC daily on date 28Feb2025.
The Problem is marked as hard, but its not actually very hard if you are familier with certain algorithm.

Problem description.

[[Shortest Common Substring]] find the shortest string that has given 2 strings as substring.

Example: str1 = "abac", str2 = "cab"
Solution: "cabac"

Initial Idea

on the surface this problem statement feels quite similer to "Least common substring problem", which requires us to find maximum length substring from given 2 strings. the solution for that requires DP (Dynamic Programming) approach. and we get the maximum common part that 2 strings have.
Maybe we can use the LCS's output in some way to find the common connecting part. and join that with remaining string to formulate a solution.

LCS implementation.

I used the standard DP implementation for LCS.

#include <iostream>
#include <vector>
using namespace std;

// Function to find and print the LCS
string longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Filling DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Backtracking to find the LCS string
    int i = m, j = n;
    string lcs;
    while (i > 0 && j > 0) {
        if (text1[i - 1] == text2[j - 1]) {  // If characters match, add to LCS
            lcs = text1[i - 1] + lcs;
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {  // Move in the direction of max value
            i--;
        } else {
            j--;
        }
    }

    return lcs;
}

Credits: chatgpt

So at the end we have the string "LCS". but we are not interesting in LCS. we want the "sieve" the LCS in between the 2 remaining strings, so that we can get the minimum possible string.

Illustration

Implementation

We want to save the common character's location in both strings.

   vector<int> ai , bi ;  
// Ai and Bi save the location of LCS in both A , and B resp.
        while(i > 0 &&  j > 0) {
            if ( a[i-1] == b[j-1]) {

                ai.push_back(i-1);
                bi.push_back(j-1);
                i--;j--;
            } else if (dp[i-1][j] > dp[i][j-1]) {
                i--;
            } else {
                j--;
            }
        }

reverse both Ai and Bi, to get the indices in increasing order.

 reverse(ai.begin(), ai.end());
 reverse(bi.begin(), bi.end());

Now in the resulting string we "combine" the information from LCS , string A , and string B. like this.

        ai.push_back(n); bi.push_back(m);
        for(int i = 0 ; i < ai.size();i++) {
            while(idx_a < ai[i]) 
                lcs += a[idx_a++];
            while(idx_b < bi[i]) 
                lcs += b[idx_b++];
            idx_a++;idx_b++;
            if (ai[i] != n)
            lcs += a[ai[i]];
        }

the idea can be boiled down to these steps. first add all A's characters , then B's characters, the add the Common character, and repeat.