Number of Ways to Form a Target String Given a Dictionary | Bottom Up | Leetcode 1639 | MIK

Hi Everyone, this is the 24th video of our Playlist "Dynamic Programming : Popular Interview Problems".
In this video we will solve a very good DP problem - Number of Ways to Form a Target String Given a Dictionary | Bottom Up | Leetcode 1639 | MIK
In this video, we will solve it using Bottom Up.
The video is detailed for beginners as well so that they can understand it easily.

Problem Name : Number of Ways to Form a Target String Given a Dictionary | Bottom Up | Leetcode 1639 | MIK
Company Tags : Google, Amazon

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Video Summary :
The solution uses dynamic programming to compute the number of ways to form the target string from words. A freq table precomputes character counts for each column. The DP table dp[i][j] tracks ways to form the first i characters of target using the first j columns. Transitions handle skipping (dp[i][j+1]) or using a column (dp[i+1][j+1]). The result is in dp[m][k], ensuring efficient computation with modular arithmetic.

✨ Timelines✨
00:00 - Introduction

#MIK #mik #Mik
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #story #data #google #video #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[gui-codes]

I used to quit these Hard problems before. Thank you so much MIK.

[souravjoshi]

This is where magic happens : Hard is made Easy

[akifahmed]

I saw solutions where they have used 1D dp, if possible could you try to come up with a video on that. And all the best !!

[JJ-tpdd]

Java:
class Solution {

private int m;
private int k;

private int dp[][];
private int mod;


public int numWays(String[] words, String target) {

this.m = target.length();
this.k = words[0].length();
this.mod =

this.dp = new int[1001][1001];
//dp[i][j] = total ways to form target of length i using dicts word of each length j

long freq[][] = new long[26][k];

for(int col=0; col<k; col++) {
for(String word : words) {

char ch = word.charAt(col);
freq[ch - 'a'][col]++;
}
}

dp[0][0] = 1;

for(int i=0; i<=m; i++) {
for(int j=0; j<=k; j++) {

//not taken
if(j < k)
dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % mod;

//taken
if(i<m && j<k)
dp[i+1][j+1] = (int)(((dp[i+1][j+1] + dp[i][j]) * %mod);

}
}

return dp[m][k];
}
}

[sarthakmishra]

Maine recursion+memo se submit Kiya to TLE a raha hai

[manimanohar_]

And I think the REMAINDER you won't forget.

[MakeuPerfect]

sir please check where is the issue
class Solution {
public:
int numWays(vector<string>& words, string target) {
int m = target.length();
int k = words[0].size();
int MOD = 1e9 + 7;

vector<vector<long long>> freq(26, vector<long long>(k));
for(int col = 0; col < k; col++) {
for(string &word : words) {
freq[word[col] - 'a'][col]++;
}
}

vector<vector<long long>> dp(m + 1, vector<long long>(k + 1, 0));
dp[m][k] = 1;

for(int i = m - 1; i >= 0; i--) {
for(int j = k - 1; j >= 0; j--) {
int not_taken = dp[i][j + 1] % MOD;
int taken = (freq[target[i] - 'a'][j] * dp[i + 1][j + 1]) % MOD;
dp[i][j] = (not_taken + taken) % MOD;
}
}

return dp[0][0];
}
};