SkylineWebZ

The problem of Generating Parentheses is to find all combinations of well-formed parentheses given n pairs of parentheses. A well-formed parentheses sequence is a string consisting of n pairs of parentheses where each opening parenthesis ( is closed by a corresponding closing parenthesis ). Problem Statement: Given n, generate all combinations of well-formed parentheses that can be made using n pairs of parentheses. Example: Input: Output: [ “((()))”, “(()())”, “(())()”, “()()()”, “()(()))”] Explanation: For n = 3, there are 5 possible combinations of valid parentheses. Approach: To generate all valid parentheses combinations, we can use Backtracking. The idea is to keep track of the number of opening ( and closing ) parentheses used so far. We can add an opening parenthesis if we have not yet used n opening parentheses, and we can add a closing parenthesis if the number of closing parentheses used is less than the number of opening parentheses used. Time Complexity: Algorithm: Code Implementation in Different Languages: 1. C #include <stdio.h>#include <string.h>void generateParentheses(int n, int open, int close, char *current, char **result, int *resultIndex) { if (open == n && close == n) { result[*resultIndex] = strdup(current); (*resultIndex)++; return; } if (open < n) { current[strlen(current)] = ‘(‘; generateParentheses(n, open + 1, close, current, result, resultIndex); current[strlen(current) – 1] = ‘\0’; } if (close < open) { current[strlen(current)] = ‘)’; generateParentheses(n, open, close + 1, current, result, resultIndex); current[strlen(current) – 1] = ‘\0’; }}char** generateParenthesis(int n, int *returnSize) { char **result = (char **)malloc(sizeof(char*) * 1000); *returnSize = 0; char current[2 * n + 1]; current[0] = ‘\0’; generateParentheses(n, 0, 0, current, result, returnSize); return result;}int main() { int n = 3; int returnSize = 0; char **result = generateParenthesis(n, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i]); } return 0;} 2. C++ #include <iostream>#include <vector>#include <string>using namespace std;void generateParentheses(int n, int open, int close, string &current, vector<string> &result) { if (open == n && close == n) { result.push_back(current); return; } if (open < n) { current.push_back(‘(‘); generateParentheses(n, open + 1, close, current, result); current.pop_back(); } if (close < open) { current.push_back(‘)’); generateParentheses(n, open, close + 1, current, result); current.pop_back(); }}vector<string> generateParenthesis(int n) { vector<string> result; string current; generateParentheses(n, 0, 0, current, result); return result;}int main() { int n = 3; vector<string> result = generateParenthesis(n); for (const string &str : result) { cout << str << endl; } return 0;} 3. Java import java.util.ArrayList;import java.util.List;public class Solution { public void generateParentheses(int n, int open, int close, String current, List<String> result) { if (open == n && close == n) { result.add(current); return; } if (open < n) { generateParentheses(n, open + 1, close, current + “(“, result); } if (close < open) { generateParentheses(n, open, close + 1, current + “)”, result); } } public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); generateParentheses(n, 0, 0, “”, result); return result; } public static void main(String[] args) { Solution solution = new Solution(); List<String> result = solution.generateParenthesis(3); for (String s : result) { System.out.println(s); } }} 4. Python def generateParentheses(n: int): result = [] def backtrack(current, open, close): if open == n and close == n: result.append(current) return if open < n: backtrack(current + ‘(‘, open + 1, close) if close < open: backtrack(current + ‘)’, open, close + 1) backtrack(“”, 0, 0) return result# Test the functionprint(generateParentheses(3)) 5. C# using System;using System.Collections.Generic;public class Solution { public void GenerateParentheses(int n, int open, int close, string current, List<string> result) { if (open == n && close == n) { result.Add(current); return; } if (open < n) { GenerateParentheses(n, open + 1, close, current + “(“, result); } if (close < open) { GenerateParentheses(n, open, close + 1, current + “)”, result); } } public List<string> GenerateParenthesis(int n) { List<string> result = new List<string>(); GenerateParentheses(n, 0, 0, “”, result); return result; } public static void Main() { Solution solution = new Solution(); List<string> result = solution.GenerateParenthesis(3); foreach (string s in result) { Console.WriteLine(s); } }} 6. JavaScript var generateParenthesis = function(n) { const result = []; function backtrack(current, open, close) { if (open === n && close === n) { result.push(current); return; } if (open < n) { backtrack(current + ‘(‘, open + 1, close); } if (close < open) { backtrack(current + ‘)’, open, close + 1); } } backtrack(“”, 0, 0); return result;};// Test the functionconsole.log(generateParenthesis(3)); Conclusion:

Problem Statement: Given a string s and a pattern p, implement a regular expression matching algorithm to determine if s matches p. The pattern may include the characters: The matching should cover the entire string (not just a substring). Example: Input: Output: Explanation: The pattern a* matches zero or more a‘s. In this case, the pattern a* matches the string “aa”. Input: Output: Explanation: The pattern doesn’t match the string. Approach: This problem can be efficiently solved using Dynamic Programming (DP). The idea is to build a 2D DP table where each entry dp[i][j] represents whether the substring s[0..i-1] matches the pattern p[0..j-1]. Time Complexity: Space Complexity: Algorithm: Code Implementation: 1. C #include <stdio.h>#include <stdbool.h>#include <string.h>bool isMatch(char* s, char* p) { int m = strlen(s), n = strlen(p); bool dp[m+1][n+1]; dp[0][0] = true; for (int j = 1; j <= n; j++) { dp[0][j] = (p[j-1] == ‘*’ && dp[0][j-2]); } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘.’) { dp[i][j] = dp[i-1][j-1]; } else if (p[j-1] == ‘*’) { dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == ‘.’) && dp[i-1][j]); } else { dp[i][j] = false; } } } return dp[m][n];}int main() { char s[] = “aa”; char p[] = “a*”; printf(“%s\n”, isMatch(s, p) ? “True” : “False”); return 0;} 2. C++ #include <iostream>#include <vector>#include <cstring>using namespace std;bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector<vector<bool>> dp(m+1, vector<bool>(n+1, false)); dp[0][0] = true; for (int j = 1; j <= n; j++) { if (p[j-1] == ‘*’) { dp[0][j] = dp[0][j-2]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘.’) { dp[i][j] = dp[i-1][j-1]; } else if (p[j-1] == ‘*’) { dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == ‘.’)); } } } return dp[m][n];}int main() { string s = “aa”; string p = “a*”; cout << (isMatch(s, p) ? “True” : “False”) << endl; return 0;} 3. Java public class Solution { public boolean isMatch(String s, String p) { int m = s.length(), n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int j = 1; j <= n; j++) { if (p.charAt(j – 1) == ‘*’) { dp[0][j] = dp[0][j – 2]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p.charAt(j – 1) == s.charAt(i – 1) || p.charAt(j – 1) == ‘.’) { dp[i][j] = dp[i – 1][j – 1]; } else if (p.charAt(j – 1) == ‘*’) { dp[i][j] = dp[i][j – 2] || (dp[i – 1][j] && (s.charAt(i – 1) == p.charAt(j – 2) || p.charAt(j – 2) == ‘.’)); } } } return dp[m][n]; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.isMatch(“aa”, “a*”)); // Output: true }} 4. Python def isMatch(s: str, p: str) -> bool: m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for j in range(1, n + 1): if p[j – 1] == ‘*’: dp[0][j] = dp[0][j – 2] for i in range(1, m + 1): for j in range(1, n + 1): if p[j – 1] == s[i – 1] or p[j – 1] == ‘.’: dp[i][j] = dp[i – 1][j – 1] elif p[j – 1] == ‘*’: dp[i][j] = dp[i][j – 2] or (dp[i – 1][j] and (s[i – 1] == p[j – 2] or p[j – 2] == ‘.’)) return dp[m][n]# Test the functionprint(isMatch(“aa”, “a*”)) # Output: True 5. C# using System;public class Solution { public bool IsMatch(string s, string p) { int m = s.Length, n = p.Length; bool[,] dp = new bool[m + 1, n + 1]; dp[0, 0] = true; for (int j = 1; j <= n; j++) { if (p[j – 1] == ‘*’) { dp[0, j] = dp[0, j – 2]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j – 1] == s[i – 1] || p[j – 1] == ‘.’) { dp[i, j] = dp[i – 1, j – 1]; } else if (p[j – 1] == ‘*’) { dp[i, j] = dp[i, j – 2] || (dp[i – 1, j] && (s[i – 1] == p[j – 2] || p[j – 2] == ‘.’)); } } } return dp[m, n]; } public static void Main() { Solution solution = new Solution(); Console.WriteLine(solution.IsMatch(“aa”, “a*”)); // Output: True }} 6. JavaScript var isMatch = function(s, p) { const m = s.length, n = p.length; const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(false)); dp[0][0] = true; for (let j = 1; j <= n; j++) { if (p[j – 1] === ‘*’) { dp[0][j] = dp[0][j – 2]; } } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (p[j – 1] === s[i – 1] || p[j – 1] === ‘.’) { dp[i][j] = dp[i – 1][j – 1]; } else if (p[j – 1] === ‘*’) { dp[i][j] = dp[i][j – 2] || (dp[i – 1][j] && (s[i – 1] === p[j – 2] || p[j – 2] === ‘.’)); } } } return dp[m][n];};// Test the functionconsole.log(isMatch(“aa”, “a*”)); // Output: true Conclusion: This algorithm efficiently solves the problem of regular expression matching using Dynamic Programming (DP). The DP approach ensures that we check all possible ways a substring of s can match the pattern p. The time and space complexities are O(m * n), where m and n are the lengths of the string and the pattern, respectively.

Problem Statement: Given a string s, find the longest palindromic substring in s. A palindrome is a string that reads the same forwards and backwards. You need to return the longest palindromic substring. Example: Example 1: Input:s = “babad” Output:”bab”(Note: “aba” is also a valid answer.) Example 2: Input:s = “cbbd” Output:”bb” Approach: We can solve this problem using Dynamic Programming (DP). The idea is to build a 2D table dp, where each entry dp[i][j] represents whether the substring s[i…j] is a palindrome. If dp[i][j] is True, it means that the substring s[i…j] is a palindrome. The transitions are as follows: Time Complexity: Algorithm: Code Implementation in Different Languages: 1. C: #include <stdio.h>#include <string.h>char* longestPalindrome(char* s) { int n = strlen(s); if (n == 0) return “”; int dp[n][n]; memset(dp, 0, sizeof(dp)); int start = 0, maxLength = 1; for (int i = 0; i < n; i++) { dp[i][i] = 1; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n – length + 1; i++) { int j = i + length – 1; if (s[i] == s[j] && (length == 2 || dp[i + 1][j – 1])) { dp[i][j] = 1; if (length > maxLength) { start = i; maxLength = length; } } } } char* result = (char*)malloc((maxLength + 1) * sizeof(char)); strncpy(result, s + start, maxLength); result[maxLength] = ‘\0’; return result;}int main() { char s[] = “babad”; printf(“Longest Palindromic Substring: %s\n”, longestPalindrome(s)); return 0;} 2. C++: #include <iostream>#include <vector>#include <cstring>using namespace std;string longestPalindrome(string s) { int n = s.length(); if (n == 0) return “”; vector<vector<bool>> dp(n, vector<bool>(n, false)); int start = 0, maxLength = 1; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n – length + 1; i++) { int j = i + length – 1; if (s[i] == s[j] && (length == 2 || dp[i + 1][j – 1])) { dp[i][j] = true; if (length > maxLength) { start = i; maxLength = length; } } } } return s.substr(start, maxLength);}int main() { string s = “babad”; cout << “Longest Palindromic Substring: ” << longestPalindrome(s) << endl; return 0;} 3. Java: public class Solution { public String longestPalindrome(String s) { int n = s.length(); if (n == 0) return “”; boolean[][] dp = new boolean[n][n]; int start = 0, maxLength = 1; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n – length + 1; i++) { int j = i + length – 1; if (s.charAt(i) == s.charAt(j) && (length == 2 || dp[i + 1][j – 1])) { dp[i][j] = true; if (length > maxLength) { start = i; maxLength = length; } } } } return s.substring(start, start + maxLength); } public static void main(String[] args) { Solution sol = new Solution(); String s = “babad”; System.out.println(“Longest Palindromic Substring: ” + sol.longestPalindrome(s)); }} 4. Python: def longestPalindrome(s: str) -> str: n = len(s) if n == 0: return “” dp = [[False] * n for _ in range(n)] start, maxLength = 0, 1 for i in range(n): dp[i][i] = True for length in range(2, n + 1): for i in range(n – length + 1): j = i + length – 1 if s[i] == s[j] and (length == 2 or dp[i + 1][j – 1]): dp[i][j] = True if length > maxLength: start = i maxLength = length return s[start:start + maxLength]# Tests = “babad”print(“Longest Palindromic Substring:”, longestPalindrome(s)) 5. C#: using System;public class Solution { public string LongestPalindrome(string s) { int n = s.Length; if (n == 0) return “”; bool[,] dp = new bool[n, n]; int start = 0, maxLength = 1; for (int i = 0; i < n; i++) { dp[i, i] = true; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n – length + 1; i++) { int j = i + length – 1; if (s[i] == s[j] && (length == 2 || dp[i + 1, j – 1])) { dp[i, j] = true; if (length > maxLength) { start = i; maxLength = length; } } } } return s.Substring(start, maxLength); } public static void Main(string[] args) { Solution sol = new Solution(); string s = “babad”; Console.WriteLine(“Longest Palindromic Substring: ” + sol.LongestPalindrome(s)); }} 6. JavaScript: var longestPalindrome = function(s) { const n = s.length; if (n === 0) return “”; const dp = Array.from({ length: n }, () => Array(n).fill(false)); let start = 0, maxLength = 1; for (let i = 0; i < n; i++) { dp[i][i] = true; } for (let length = 2; length <= n; length++) { for (let i = 0; i < n – length + 1; i++) { const j = i + length – 1; if (s[i] === s[j] && (length === 2 || dp[i + 1][j – 1])) { dp[i][j] = true; if (length > maxLength) { start = i; maxLength = length; } } } } return s.substring(start, start + maxLength);};// Testlet s = “babad”;console.log(“Longest Palindromic Substring:”, longestPalindrome(s)); Summary:

Utilizing Hash Map – O(n) Time and O(n) Space Pre-order TraversalThough instead of linearly looking for every node in the in-order array, we can utilize hashing in line with first technique. Plot the indices of in-order arrays against their values. This will simplify searches from O(n) to O(1). C++ Java Python C# Output 3 4 1 5 2 0

Given pre-order and in-order traversals of a Binary Tree, the challenge is to build the tree and retrieve its root. Table of Content [Naive Approach] Using Pre-order traversal – O(n^2) Time and O(h) Space Pre-order traversal will help one build the tree. Create root node by first element of the pre-order array. In the in-order array, determine this node’s index. Create the left subtree in-order using the components on the left side of the root node. Likewise build the appropriate subtree in-order using the items on the right side of the root node. C++ Java Python C# Output 3 4 1 5 2 0

Making Use of Merge of MergeSortMerge function of Merge sort is supposed to be used here. Consider two sorted arrays, Array 1 and Array 2, together with an empty array, Array 3. Here “i” pointer refers towards 0th index of Array1, similarly “j” and “k” pointer points towards 0th index of Array2 and Array3 for comparisons. C++ C Java Python JavaScript Output 1 2 3 4 5 6 7 8 Time Complexity : O(n1 + n2) Auxiliary Space : O(n1 + n2)

Using Self Balancing BST: C++ C Java Python Output 1 2 3 4 5 6 7 8 Time Complexity: O((n1 + n2)* Log(n1 + n2))Auxiliary Space: O(n1 + n2) for the tree map.

Merging two sorted arrays is the challenge here in a sorted way. Examples:  Input: arr1[] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8} Output: arr3[] = {1, 2, 3, 4, 4, 5, 6, 8} Input: arr1[] = { 5, 8, 9}, arr2[] = {4, 7, 8} Output: arr3[] = {4, 5, 7, 8, 8, 9}  Table of Content The naïve approach to accomplish the same is physical force. Combine all of arr 1’s and arr 2’s components in arr 3. Sort the arr3 then just once more. C++ C Java Python Output 1 2 3 4 5 6 7 8 Time Complexity : O((n1 + n2) log(n1 + n2)) , the whole size of arr3 is m+nAuxiliary Space: O(1)