SkylineWebZ

The problem “Distinct Subsequences“ asks for the number of distinct subsequences of a string s that match a string t. This is a well-known dynamic programming problem and can be efficiently solved using a 2D dynamic programming table. Problem Statement: Given a string s and a string t, find the number of distinct subsequences of s which equals t. A subsequence is derived from another string by deleting some or no characters without changing the order of the remaining characters. Example 1: Input: s = “rabbbit”, t = “rabbit” Output: 3 Explanation: There are three distinct subsequences of “rabbbit” which equal “rabbit”: Example 2: Input: s = “axaxb”, t = “ab” Output: 4 Explanation: There are four distinct subsequences of “axaxb” which equal “ab”: Approach: We use a dynamic programming approach to solve this problem. Let dp[i][j] represent the number of ways to form the first j characters of t using the first i characters of s. The recurrence relation is as follows: The final answer is dp[len(s)][len(t)]. Time Complexity: Now, let’s implement this solution in different languages. C Code: #include <stdio.h>#include <string.h>int numDistinct(char *s, char *t) { int m = strlen(s), n = strlen(t); int dp[m+1][n+1]; // Initialize the dp array for (int i = 0; i <= m; i++) { dp[i][0] = 1; // There’s 1 way to form empty t } for (int j = 1; j <= n; j++) { dp[0][j] = 0; // There’s no way to form a non-empty t from empty s } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i-1] == t[j-1]) { dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; } else { dp[i][j] = dp[i-1][j]; } } } return dp[m][n];}int main() { char s[] = “rabbbit”, t[] = “rabbit”; printf(“Number of distinct subsequences: %d\n”, numDistinct(s, t)); return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;int numDistinct(string s, string t) { int m = s.length(), n = t.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // Base case: dp[i][0] = 1 for (int i = 0; i <= m; i++) { dp[i][0] = 1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i – 1] == t[j – 1]) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n];}int main() { string s = “rabbbit”, t = “rabbit”; cout << “Number of distinct subsequences: ” << numDistinct(s, t) << endl; return 0;} Java Code: public class Main { public static int numDistinct(String s, String t) { int m = s.length(), n = t.length(); int[][] dp = new int[m + 1][n + 1]; // Base case: dp[i][0] = 1 for (int i = 0; i <= m; i++) { dp[i][0] = 1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s.charAt(i – 1) == t.charAt(j – 1)) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n]; } public static void main(String[] args) { String s = “rabbbit”, t = “rabbit”; System.out.println(“Number of distinct subsequences: ” + numDistinct(s, t)); }} Python Code: def numDistinct(s, t): m, n = len(s), len(t) dp = [[0] * (n + 1) for _ in range(m + 1)] # Base case: dp[i][0] = 1 for i in range(m + 1): dp[i][0] = 1 for i in range(1, m + 1): for j in range(1, n + 1): if s[i – 1] == t[j – 1]: dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j] else: dp[i][j] = dp[i – 1][j] return dp[m][n]# Test cases = “rabbbit”t = “rabbit”print(“Number of distinct subsequences:”, numDistinct(s, t)) C# Code: using System;class Program { public static int NumDistinct(string s, string t) { int m = s.Length, n = t.Length; int[,] dp = new int[m + 1, n + 1]; // Base case: dp[i][0] = 1 for (int i = 0; i <= m; i++) { dp[i, 0] = 1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i – 1] == t[j – 1]) { dp[i, j] = dp[i – 1, j – 1] + dp[i – 1, j]; } else { dp[i, j] = dp[i – 1, j]; } } } return dp[m, n]; } static void Main() { string s = “rabbbit”, t = “rabbit”; Console.WriteLine(“Number of distinct subsequences: ” + NumDistinct(s, t)); }} JavaScript Code: function numDistinct(s, t) { const m = s.length, n = t.length; let dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0)); // Base case: dp[i][0] = 1 for (let i = 0; i <= m; i++) { dp[i][0] = 1; } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (s[i – 1] === t[j – 1]) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n];}// Test caseconst s = “rabbbit”, t = “rabbit”;console.log(“Number of distinct subsequences:”, numDistinct(s, t)); Summary: This problem can be efficiently solved using dynamic programming, and the code above provides solutions for C, C++, Java, Python, C#, and JavaScript. The time complexity for all the solutions is O(m×n)O(m \times n)O(m×n), where mmm and nnn are the lengths of strings s and t, respectively.

Determine the biggest rectangular area a given histogram can have where a number of adjacent bars allow the biggest rectangle to be formed. Assume for simplicity that the width of all bars is one unit. Take the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6} for instance. Twelve is the largest rectangle that may be formed; the max area rectangle is underlined in red below. One may find a straightforward solution by first considering all bars as points of reference and then computing the area of every rectangle beginning with each bar. At last return maximum of all conceivable areas. O(n^2) would be the time complexity of this solution. Solving this in O(nLogn) time will require Divide and Conquer. Finding the least value in the given array is the aim. The maximum area follows three values once we have index of the minimum value. C++ Java Python C# Output Maximum area is 12 Time Complexity: O(N log N) Auxiliary Space: O(N)

This method mostly serves as an optimization over the last one. The optimizations follow from below observations. We pop one item from the stack and mark current item as next smaller of it while computing next smaller element. Here, one significant note is the item below each item in the stack—the former smaller element. We thus do not have to specifically compute previous smaller. The thorough implementation steps are listed here. C++ C Java Python Output 100

The concept rests on the innocent attitude. We find previous smaller and next smaller for the entire array in linear time instead of linearly finding previous smaller and next smaller for every element. C++ C Java python C# JavaScript

In a given histogram, find the greatest rectangular area that can be formed by a number of contiguous bars with heights provided in an array. Assume for the sake of simplicity that the width of each bar is one unit. Table of Content Simple Approach: O(n^2) Time as well as O(1) Space C++ C Java Python C# JavaScript Output 100

The problem statement is as follows: given a goal value k and an integer array arr of size N, sorted in ascending order (may contain identical values). The array is now rotated at an unidentified pivot point. If k is present, return True; if not, return False. Solution: In a sorted array, how does rotation take place?Consider the following sorted array: {1, 2, 3, 4, 5}. This array will become {4, 5, 1, 2, 3} if we rotate it at index 3. Essentially, we shifted the remaining components to the right and the element at the last index to the front. This procedure was carried out twice. Brute Force Approach The linear search method is one simple strategy we can take into account. In order to determine whether the target is present in the array, we will use this technique to traverse it. We shall just return True if it is found; if not, we will return False. Algorithm: C++ Java Python JavaScript Output: Target is present in the array.Complexity Analysis Time Complexity: O(N), N = size of the given array. Space Complexity: O(1)

This is an iterative method for the recursive method that was previously explained. Here, we attempt to move iteratively in a single direction for every cell. C++ Java python JavaScript

Finding every instance of a given word in a 2D grid with m*n characters is the work at hand. At any given time, a word can be matched in all eight directions. If every character in a word matches in that direction (not in zigzag form), the word is considered to be found in that direction.Horizontally left, horizontally right, vertically up, vertically down, and four diagonal directions are the eight directions. Note: The lexicographically smallest list should be the one that returns. The coordinates should only appear once in the list if the word may be discovered in several directions beginning from the same coordinates. For instance: Table of Content Using Recursion – O(m*n*k) Time and O(k) Space To locate the word, travel to each grid cell and look in all eight directions (up, down, left, right, and diagonals). We also attempt to travel in a single direction for every cell. C++ Java Python C# JavaScript Output {0,0} {0,2} {1,0} Time Complexity: O(m*n*k), where m is the number of rows, n is the number of columns and k is the length of word.Auxiliary Space: O(k), recursion stack space.