String manipulation is a cornerstone of computer science, often surfacing in real-world applications such as text processing and data analysis.
One such intriguing problem is finding Distinct Subsequences, which tests your ability to handle dynamic programming and combinatorics.
Given two strings s and t, determine how many distinct subsequences of s are equal to t.
Input:s = "caaat", t = "cat"
Output: 3
Here, “cat” can be formed in three different ways from s.
Input:s = "xxyxy", t = "xy"
Output: 5
There are five ways to form “xy” from s.
s and t range from 1 to 1000.s and t consist of lowercase English letters.This problem challenges you to identify overlapping subproblems and use efficient techniques like dynamic programming to solve them. It highlights how subtle variations in character sequences can lead to vastly different outcomes.
Whether you’re preparing for coding interviews or honing your algorithmic skills, tackling the distinct subsequences problem is a great way to deepen your understanding of string manipulation.
Explanation:
Explanation: There are 3 different ways to sum the input numbers to get a sum of 2.
+2 +2 -2 = 2
+2 -2 +2 = 2
-2 +2 +2 = 2
Constraints:
To solve the interleaving string problem, one might consider using a dynamic programming or recursive approach to evaluate all possible ways to combine the strings.
class Solution:
def numDistinct(self, s: str, t: str) -> int:
if len(t) > len(s):
return 0
def dfs(i, j):
if j == len(t):
return 1
if i == len(s):
return 0
res = dfs(i + 1, j)
if s[i] == t[j]:
res += dfs(i + 1, j + 1)
return res
return dfs(0, 0)class Solution {
public:
int numDistinct(string s, string t) {
if (t.length() > s.length()) {
return 0;
}
return dfs(s, t, 0, 0);
}
private:
int dfs(const string &s, const string &t, int i, int j) {
if (j == t.length()) {
return 1;
}
if (i == s.length()) {
return 0;
}
int res = dfs(s, t, i + 1, j);
if (s[i] == t[j]) {
res += dfs(s, t, i + 1, j + 1);
}
return res;
}
};public class Solution {
public int numDistinct(String s, String t) {
if (t.length() > s.length()) {
return 0;
}
return dfs(s, t, 0, 0);
}
private int dfs(String s, String t, int i, int j) {
if (j == t.length()) {
return 1;
}
if (i == s.length()) {
return 0;
}
int res = dfs(s, t, i + 1, j);
if (s.charAt(i) == t.charAt(j)) {
res += dfs(s, t, i + 1, j + 1);
}
return res;
}
}class Solution {
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
numDistinct(s, t) {
if (t.length > s.length) {
return 0;
}
const dfs = (i, j) => {
if (j === t.length) {
return 1;
}
if (i === s.length) {
return 0;
}
let res = dfs(i + 1, j);
if (s[i] === t[j]) {
res += dfs(i + 1, j + 1);
}
return res;
}
return dfs(0, 0);
}
}class Solution:
def numDistinct(self, s: str, t: str) -> int:
if len(t) > len(s):
return 0
dp = {}
def dfs(i, j):
if j == len(t):
return 1
if i == len(s):
return 0
if (i, j) in dp:
return dp[(i, j)]
res = dfs(i + 1, j)
if s[i] == t[j]:
res += dfs(i + 1, j + 1)
dp[(i, j)] = res
return res
return dfs(0, 0)public class Solution {
private int[][] dp;
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
if (n > m) return 0;
dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
Arrays.fill(dp[i], -1);
}
return dfs(s, t, 0, 0);
}
private int dfs(String s, String t, int i, int j) {
if (j == t.length()) return 1;
if (i == s.length()) return 0;
if (dp[i][j] != -1) return dp[i][j];
int res = dfs(s, t, i + 1, j);
if (s.charAt(i) == t.charAt(j)) {
res += dfs(s, t, i + 1, j + 1);
}
dp[i][j] = res;
return res;
}
}
class Solution {
vector> dp;
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
if (n > m) return 0;
dp.assign(m + 1, vector(n + 1, -1));
return dfs(s, t, 0, 0);
}
private:
int dfs(const string &s, const string &t, int i, int j) {
if (j == t.size()) return 1;
if (i == s.size()) return 0;
if (dp[i][j] != -1) return dp[i][j];
int res = dfs(s, t, i + 1, j);
if (s[i] == t[j]) {
res += dfs(s, t, i + 1, j + 1);
}
dp[i][j] = res;
return res;
}
}; class Solution {
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
numDistinct(s, t) {
let m = s.length, n = t.length;
if (n > m) return 0;
let dp = Array(m + 1).fill().map(() =>
Array(n + 1).fill(-1));
const dfs = (i, j) => {
if (j === n) return 1;
if (i === m) return 0;
if (dp[i][j] !== -1) return dp[i][j];
let res = dfs(i + 1, j);
if (s[i] === t[j]) {
res += dfs(i + 1, j + 1);
}
dp[i][j] = res;
return res;
}
return dfs(0, 0);
}
}class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][n] = 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
dp[i][j] = dp[i + 1][j]
if s[i] == t[j]:
dp[i][j] += dp[i + 1][j + 1]
return dp[0][0]public class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][n] = 1;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (s.charAt(i) == t.charAt(j)) {
dp[i][j] += dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
}
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.length(), n = t.length();
vector> dp(m + 1, vector(n + 1, 0));
for (int i = 0; i <= m; i++) {
dp[i][n] = 1;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (s[i] == t[j]) {
dp[i][j] += dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
}; class Solution {
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
numDistinct(s, t) {
let m = s.length, n = t.length;
let dp = Array.from({ length: m + 1 }, () =>
Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) {
dp[i][n] = 1;
}
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (s[i] === t[j]) {
dp[i][j] += dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
}class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][n] = 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
dp[i][j] = dp[i + 1][j]
if s[i] == t[j]:
dp[i][j] += dp[i + 1][j + 1]
return dp[0][0]public class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[] dp = new int[n + 1];
int[] nextDp = new int[n + 1];
dp[n] = nextDp[n] = 1;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
nextDp[j] = dp[j];
if (s.charAt(i) == t.charAt(j)) {
nextDp[j] += dp[j + 1];
}
}
dp = nextDp.clone();
}
return dp[0];
}
}class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
vector dp(n + 1, 0);
vector nextDp(n + 1, 0);
dp[n] = nextDp[n] = 1;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
nextDp[j] = dp[j];
if (s[i] == t[j]) {
nextDp[j] += dp[j + 1];
}
}
dp = nextDp;
}
return dp[0];
}
}; class Solution {
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
numDistinct(s, t) {
let m = s.length, n = t.length;
let dp = new Array(n + 1).fill(0);
let nextDp = new Array(n + 1).fill(0);
dp[n] = nextDp[n] = 1;
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
nextDp[j] = dp[j];
if (s[i] === t[j]) {
nextDp[j] += dp[j + 1];
}
}
dp = nextDp.slice();
}
return dp[0];
}
}The Interleaving String problem is more than just a test of string manipulation skills; it’s a practical exercise in algorithmic thinking. It demonstrates the power of logical sequencing and helps build a strong foundation for solving real-world problems where multiple sequences or inputs need to be merged in specific ways.
By tackling problems like this, you sharpen your ability to think critically and design efficient solutions for complex challenges.
Get Hiring Updates right in your inbox from PrepInsta