algoadvance

Leetcode 3136. Valid Word

Problem Statement:

Given two strings word1 and word2, return the smallest string word such that:

1. word1 is a subsequence of word.
2. word2 is a subsequence of word.
3. word is the smallest string that satisfies the above conditions. If there are multiple valid strings, return the lexicographically smallest one.

Note:

• A string s is a subsequence of string t if deleting some characters from t (possibly none) makes s.
• Both strings consist of lowercase English letters.

Clarifying Questions:

1. What should be done if word1 and word2 are either empty strings?
   • If either string is empty, the smallest valid word should be the non-empty string.
2. Are there constraints on the length of word1 and word2?
   • Typically, this kind of problem implies reasonable constraints such as 1 ≤ len(word1), len(word2) ≤ 1000.
3. Can both word1 and word2 be the same string?
   • Yes. If they are same, the smallest valid string would be either of them, as they are identical subsequences of the final answer.

Strategy:

To address this problem, we need to determine a common supersequence. The strategy revolves around finding the shortest common supersequence (SCS) of the two strings word1 and word2.

Steps:

1. Compute the Longest Common Subsequence (LCS):
   • The LCS can help in identifying the minimum length supersequence by recognizing the common subsequence.
2. Construct the Supersequence based on LCS:
   • Using the LCS, construct the supersequence by merging word1 and word2.
   • Insert the characters from word1 and word2 while aligning with the LCS, ensuring the result is lexicographically smallest.

Code:

public class ValidWordOut {
    
    public static String smallestSupersequence(String word1, String word2) {
        int n = word1.length();
        int b = word2.length();

        // Compute the LCS dynamic programming table
        int[][] dp = new int[n + 1][b + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= b; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // Build the shortest supersequence by tracking back from dp table
        StringBuilder supersequence = new StringBuilder();
        int i = n, j = b;
        
        while (i > 0 && j > 0) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                // Part of both sequences
                supersequence.append(word1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                supersequence.append(word1.charAt(i - 1));
                i--;
            } else {
                supersequence.append(word2.charAt(j - 1));
                j--;
            }
        }
        
        // Append remaining characters of word1 or word2
        while (i > 0) {
            supersequence.append(word1.charAt(i - 1));
            i--;
        }
        
        while (j > 0) {
            supersequence.append(word2.charAt(j - 1));
            j--;
        }
        
        // Reverse the built string as we constructed it from end
        return supersequence.reverse().toString();
    }
    
    public static void main(String[] args) {
        String word1 = "abac";
        String word2 = "cab";
        System.out.println(smallestSupersequence(word1, word2)); // Output: "cabac"
    }
}

Time Complexity:

• LCS computation (DP Table Building): O(n × m), where n and m are the lengths of word1 and word2.
• Supersequence construction: O(n + m), because we traverse through both lengths once each.

Therefore, the overall time complexity of the approach is O(n × m).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?