SkylineWebZ

Problem Statement: Interleaving String Given three strings, s1, s2, and s3, determine if s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s1 and s2 is formed by inserting characters of s1 and s2 in such a way that the relative order of characters in both strings is preserved. For example: Here, s3 is an interleaving of s1 and s2, so the answer is True. Constraints: Dynamic Programming Approach We can solve this problem using a 2D DP table. Time Complexity: Code Implementation in Different Languages C: #include <stdio.h>#include <string.h>#include <stdbool.h>bool isInterleave(char *s1, char *s2, char *s3) { int m = strlen(s1); int n = strlen(s2); if (m + n != strlen(s3)) return false; bool dp[m + 1][n + 1]; memset(dp, false, sizeof(dp)); dp[0][0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && s1[i – 1] == s3[i + j – 1]) { dp[i][j] = dp[i][j] || dp[i – 1][j]; } if (j > 0 && s2[j – 1] == s3[i + j – 1]) { dp[i][j] = dp[i][j] || dp[i][j – 1]; } } } return dp[m][n];}int main() { char s1[] = “abc”; char s2[] = “def”; char s3[] = “adbcef”; if (isInterleave(s1, s2, s3)) { printf(“True\n”); } else { printf(“False\n”); } return 0;} C++: #include <iostream>#include <vector>#include <string>using namespace std;bool isInterleave(string s1, string s2, string s3) { int m = s1.size(), n = s2.size(); if (m + n != s3.size()) return false; vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); dp[0][0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && s1[i – 1] == s3[i + j – 1]) { dp[i][j] = dp[i][j] || dp[i – 1][j]; } if (j > 0 && s2[j – 1] == s3[i + j – 1]) { dp[i][j] = dp[i][j] || dp[i][j – 1]; } } } return dp[m][n];}int main() { string s1 = “abc”, s2 = “def”, s3 = “adbcef”; if (isInterleave(s1, s2, s3)) { cout << “True” << endl; } else { cout << “False” << endl; } return 0;} Java: public class Main { public static boolean isInterleave(String s1, String s2, String s3) { int m = s1.length(), n = s2.length(); if (m + n != s3.length()) return false; boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && s1.charAt(i – 1) == s3.charAt(i + j – 1)) { dp[i][j] = dp[i][j] || dp[i – 1][j]; } if (j > 0 && s2.charAt(j – 1) == s3.charAt(i + j – 1)) { dp[i][j] = dp[i][j] || dp[i][j – 1]; } } } return dp[m][n]; } public static void main(String[] args) { String s1 = “abc”, s2 = “def”, s3 = “adbcef”; System.out.println(isInterleave(s1, s2, s3) ? “True” : “False”); }} Python: def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if m + n != len(s3): return False dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for i in range(m + 1): for j in range(n + 1): if i > 0 and s1[i – 1] == s3[i + j – 1]: dp[i][j] = dp[i][j] or dp[i – 1][j] if j > 0 and s2[j – 1] == s3[i + j – 1]: dp[i][j] = dp[i][j] or dp[i][j – 1] return dp[m][n]# Example Usages1 = “abc”s2 = “def”s3 = “adbcef”print(“True” if isInterleave(s1, s2, s3) else “False”) C#: using System;class Program { public static bool IsInterleave(string s1, string s2, string s3) { int m = s1.Length, n = s2.Length; if (m + n != s3.Length) return false; bool[,] dp = new bool[m + 1, n + 1]; dp[0, 0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && s1[i – 1] == s3[i + j – 1]) { dp[i, j] = dp[i, j] || dp[i – 1, j]; } if (j > 0 && s2[j – 1] == s3[i + j – 1]) { dp[i, j] = dp[i, j] || dp[i, j – 1]; } } } return dp[m, n]; } static void Main() { string s1 = “abc”, s2 = “def”, s3 = “adbcef”; Console.WriteLine(IsInterleave(s1, s2, s3) ? “True” : “False”); }} JavaScript: function isInterleave(s1, s2, s3) { const m = s1.length, n = s2.length; if (m + n !== s3.length) return false; const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false)); dp[0][0] = true; for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { if (i > 0 && s1[i – 1] === s3[i + j – 1]) { dp[i][j] = dp[i][j] || dp[i – 1][j]; } if (j > 0 && s2[j – 1] === s3[i + j – 1]) { dp[i][j] = dp[i][j] || dp[i][j – 1]; } } } return dp[m][n];}// Example Usagelet s1 = “abc”, s2 = “def”, s3 = “adbcef”;console.log(isInterleave(s1, s2, s3) ? “True” : “False”); Summary:

Two terms of the same length, “start” and “target,” are provided in a dictionary. Determine the length of the smallest chain, if any, between “start” and “target,” such that each word in the chain is a legitimate word—that is, it appears in the dictionary—and that adjacent words in the chain differ by no more than one character. It is reasonable to assume that the “target” term is present in a dictionary and that all dictionary words have the same length. Example:  Input: Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}, start = TOON, target = PLEAOutput: 7Explanation: TOON – POON – POIN – POIE – PLIE – PLEE – PLEA Input: Dictionary = {ABCD, EBAD, EBCD, XYZA}, start = ABCV, target = EBADOutput: 4Explanation: ABCV – ABCD – EBCD – EBAD Approach: Using BFS is the suggested solution to the issue. Start with the start word and push it in a queue to determine the shortest path via BFS. Return that level of BFS traversal after the target is located for the first time. All of the phrases that can be created with that many stages are available in each BFS step. Thus, the length of the shortest word chain will be the first time the target word is discovered. C++ Java Python JS Output Length of shortest chain is: 7 Time Complexity: O(N * M), where N is the number of entries originally in the dictionary and M is the size of the string.Auxiliary Space: O(N+M)

Given a list indicating words and two separate words, startWord and targetWorda list of distinct words with comparable lengths. Determine which transformation sequences from startWord to targetWord are the shortest. They can be returned in any feasible order. The following requirements must be considered in this problem statement: Examples: Example 1: Input: startWord = “der”, targetWord = “dfs”, wordList = {“des”,”der”,”dfr”,”dgt”,”dfs”} Output: [ [ “der”, “dfr”, “dfs” ], [ “der”, “des”, “dfs”] ] Explanation: The length of the smallest transformation sequence here is 3. Following are the only two shortest ways to get to the targetWord from the startWord : “der” -> ( replace ‘r’ by ‘s’ ) -> “des” -> ( replace ‘e’ by ‘f’ ) -> “dfs”. “der” -> ( replace ‘e’ by ‘f’ ) -> “dfr” -> ( replace ‘r’ by ‘s’ ) -> “dfs”. Example 2: Input: startWord = “gedk”, targetWord= “geek” wordList = {“geek”, “gefk”} Output: [ [ “gedk”, “geek” ] ] Explanation: The length of the smallest transformation sequence here is 2. Following is the only shortest way to get to the targetWord from the startWord : “gedk” -> ( replace ‘d’ by ‘e’ ) -> “geek”. Intuition: The idea behind applying the BFS traversal strategy to these types of issues is that, if we pay close attention, we continue to replace the characters one by one, giving the impression that we are going level-wise to get to the targetWord. It is evident from the example below that there are two ways to get to the targetWord. Since we require all of the shortest sequences to get to the destination word, unlike the prior case, we continue the traversal for as many instances of the targetWord as possible rather than stopping it at the first occurrence. The only difficulty here is that, even if a word matches the changed word during character replacement, we do not have to remove it from the wordList right away. Rather, we remove it whenever the traversal for a specific level is over, enabling us to investigate every potential route. This enables us to find several sequences using related words that lead to the targetWord. We can infer from the preceding image that there are two shortest feasible sequences that lead to the word “cog.” C++ Java Output:  der des dfs  der dfr dfs

The objective is to identify the smallest substring in S that contains every character of P, including duplicates, given two strings S (length m) and P (length n). Return “-1” if there isn’t a substring of that kind. Return the substring with the least starting index if more than one of the same length is found. Examples:  Input: S = “timetopractice”, P = “toc”Output: topracExplanation: “toprac” is the smallest substring in which “toc” can be found. Input: S = “zoomlazapzo”, P = “oza”Output: apzoExplanation: “apzo” is the smallest substring in which “oza” can be found. Table of Content [Naive Method] O(N^3) by Generating Every Substring O(N) Space and Time: Creating every feasible substring from the provided string S and determining if each substring contains every character in the string P is the fundamental principle behind solving this challenge. A helper function that counts the frequency of each character in P and compares it to the frequency of the selected substring can accomplish this checking. The shortest substring is updated in accordance with the current minimum length if a substring contains every character of the P. Until every substring has been examined, the procedure is repeated. C++ C Java Python JS Output toprac Time Complexity: O(N3)Auxiliary Space: O(N) to create substrings.

The aim is to set all rows and columns to zeroes in a constant space complexity matrix of size M x N if a certain element is zero. Examples: Input: [ [1, 1, 1],[1, 0, 1],[1, 1, 1]]Output: [ [1, 0, 1],[0, 0, 0],[1, 0, 1]]Explanation: one zero is present at cell(2,2), and all the elements in the 2nd row and 2nd column are marked as zeroes. Input: [[ 0, 1, 2, 0],[3, 4, 5, 2],[1, 3, 1, 5]]Output: [[0, 0, 0, 0],[0, 4, 5, 0],[0, 3, 1, 0]]Explanation: There are zeroes present in the 1st row at 1st column and 4th column. Native method: C++ Java Python3 JS Output 0 0 0 0 0 4 5 0 0 3 1 0 Time Complexity: O((N*M)*(N + M)) + O(N*M),

The concept is to note the presence of elements inside the same array. Since 1 is the smallest positive integer, first we look to see whether 1 is there; should it be absent, the response is 1. All numbers that are either negative or greater than the array size are converted to 1 otherwise to maintain all numbers within a range of 1 to n. We next index the numbers using their values. To indicate the presence of a number x, we are adding n to the number existing at index x – 1. At last, we search the array for the first unmarked index to obtain the smallest missing positive value. C++ C Java Python JS Output 3

First, all positive integers should be migrated to the left side of the array. We next traverse over this left segment and negating the value at index (x – 1) marks the occurrences of every number x. Finally, go over the left segment once more and, looking for the first unmarked piece, determine the missing number. Examples: Input:  arr[] = {2, -3, 4, 1, 1, 7}Output: 3Explanation: 3 is the smallest positive number missing from the array. Input:  arr[] = {5, 3, 2, 5, 1}Output: 4Explanation: 4 is the smallest positive number missing from the array. Input: arr[] = {-8, 0, -1, -4, -3}Output: 1Explanation: 1 is the smallest positive number missing from the array. C++ C Java Python JS Output 3

The concept is like Cycle Sort and moves every element in the array to its proper place depending on its value. Thus, for any number, say x, arrange 1 ≤ x ≤ n at the (x – 1)th index. At last, go over the array looking for whether the numbers match the predicted indexes or not. The first missing positive number results from the first spot where the number does not match its index. The smallest missing positive integer is n + 1, if all the numbers from 1 to n match their proper indices. C++ C Java Python JS Output 3

The visited array will help to track which integers from the original array were present. We note the matching place in the visited array for every positive number in the input array. We then search the visited array looking for the first unvisited point. The first unvisited index reveals the initial missing positive number.We are simply noting numbers falling between 1 and n here. C++ C Java Python JavaScript Output 3

The objective is to determine the smallest positive number that is absent from an unsorted array arr[] that contains both positive and negative items. Note: The initial array is modifiable. Examples: Input: arr[] = {2, -3, 4, 1, 1, 7}Output: 3Explanation: 3 is the smallest positive number missing from the array. Input: arr[] = {5, 3, 2, 5, 1}Output: 4Explanation: 4 is the smallest positive number missing from the array. Input: arr[] = {-8, 0, -1, -4, -3}Output: 1Explanation: 1 is the smallest positive number missing from the array. Table of Content [Naive approach] By Sorting – O(n*log n) Time and O(n) Space Sorting the array will help one to presume a missing number as 1. Now go over the array iteratively and for every element arr[i], Should arr[i] be a missing number, increase missing number by one.Proceed to hunt for the missing number if arr[i] < missing number.Should arr[i] surpass the missing number, break and provide the missing number back. C++ C Java Python JS Output 3