Bitmasking approach
In the bitmasking approach, represent each subsequence as a bitmask, where each bit corresponds to whether an element is included or not. Iterate through all possible bitmasks, counting unique ones to find distinct subsequences efficiently.
Example: In this example The function counts distinct subsequences of a string ‘s’ using a bitmasking approach, avoiding duplicates by storing results in a set.
function countDistinctSubsequences(s) {
let sn = new Set();
for (let mask = 0; mask < (1 << s.length); mask++) {
let subsequence = "";
for (let i = 0; i < s.length; i++) {
if ((mask & (1 << i)) !== 0) {
subsequence += s[i];
}
}
sn.add(subsequence);
}
return sn.size;
}
let str = "gfg";
console.log(countDistinctSubsequences(str));
Output
7
JavaScript Program to Count Distinct Subsequences
In this article, we are going to learn about Count Distinct Subsequences in JavaScript. Counting distinct subsequences refers to determining the number of unique non-empty subarrays or subsequence combinations within a given sequence or string, without repetition of elements or order.
Example:
Input : str = "gfg"
Output : 7
The seven distinct subsequences are "", "g", "f",
"gf", "fg", "gg" and "gfg"
We will explore all the above methods along with their basic implementation with the help of examples.
Table of Content
- Using Recursion
- Using dynamic programming with a for…of loop
- Bitmasking approach
- Using Set to Track Subsequences