DSA

The Trapping Rain Water problem asks us to compute how much water can be trapped between bars of varying heights after it rains. The problem typically provides an array where each element represents the height of a bar, and we need to calculate how much water can be stored between these bars. Problem Statement: Given an array height[] representing the height of bars in a histogram, the task is to compute the amount of water that can be trapped between the bars after raining. Example: Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6Explanation: The total water trapped is 6 units. Example 2: Input: height = [4,2,0,3,2,5]Output: 9 Approach: To solve this problem efficiently, we can use the two-pointer technique combined with precomputed maximum heights. Here’s a breakdown of the approach: Time Complexity: Code Implementations: 1. C: #include <stdio.h>int trap(int* height, int heightSize) { if (heightSize == 0) return 0; int left = 0, right = heightSize – 1; int left_max = 0, right_max = 0; int water_trapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { water_trapped += left_max – height[left]; } left++; } else { if (height[right] >= right_max) { right_max = height[right]; } else { water_trapped += right_max – height[right]; } right–; } } return water_trapped;}int main() { int height[] = {0,1,0,2,1,0,1,3,2,1,2,1}; int size = sizeof(height) / sizeof(height[0]); printf(“Trapped Water: %d\n”, trap(height, size)); return 0;} 2. C++: #include <iostream>#include <vector>using namespace std;int trap(vector<int>& height) { int n = height.size(); if (n == 0) return 0; int left = 0, right = n – 1; int left_max = 0, right_max = 0; int water_trapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { water_trapped += left_max – height[left]; } left++; } else { if (height[right] >= right_max) { right_max = height[right]; } else { water_trapped += right_max – height[right]; } right–; } } return water_trapped;}int main() { vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1}; cout << “Trapped Water: ” << trap(height) << endl; return 0;} 3. Java: public class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) return 0; int left = 0, right = n – 1; int leftMax = 0, rightMax = 0; int waterTrapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { waterTrapped += leftMax – height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { waterTrapped += rightMax – height[right]; } right–; } } return waterTrapped; } public static void main(String[] args) { Solution solution = new Solution(); int[] height = {0,1,0,2,1,0,1,3,2,1,2,1}; System.out.println(“Trapped Water: ” + solution.trap(height)); }} 4. Python: def trap(height): if not height: return 0 left, right = 0, len(height) – 1 left_max, right_max = 0, 0 water_trapped = 0 while left <= right: if height[left] <= height[right]: if height[left] >= left_max: left_max = height[left] else: water_trapped += left_max – height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water_trapped += right_max – height[right] right -= 1 return water_trapped# Example usageheight = [0,1,0,2,1,0,1,3,2,1,2,1]print(f”Trapped Water: {trap(height)}”) 5. C#: using System;public class Solution { public int Trap(int[] height) { int n = height.Length; if (n == 0) return 0; int left = 0, right = n – 1; int leftMax = 0, rightMax = 0; int waterTrapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { waterTrapped += leftMax – height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { waterTrapped += rightMax – height[right]; } right–; } } return waterTrapped; } public static void Main(string[] args) { Solution solution = new Solution(); int[] height = {0,1,0,2,1,0,1,3,2,1,2,1}; Console.WriteLine(“Trapped Water: ” + solution.Trap(height)); }} 6. JavaScript: var trap = function(height) { let n = height.length; if (n === 0) return 0; let left = 0, right = n – 1; let leftMax = 0, rightMax = 0; let waterTrapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { waterTrapped += leftMax – height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { waterTrapped += rightMax – height[right]; } right–; } } return waterTrapped;};// Example usageconst height = [0,1,0,2,1,0,1,3,2,1,2,1];console.log(“Trapped Water: “, trap(height)); Summary:

Problem Statement: Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring. A valid parentheses string is: Example: Example 1: Example 2: Example 3: Approach (Using Dynamic Programming): Time Complexity: Code in Different Languages: 1. C #include <stdio.h>#include <string.h>int longestValidParentheses(char* s) { int n = strlen(s); int dp[n]; memset(dp, 0, sizeof(dp)); int maxLength = 0; for (int i = 1; i < n; i++) { if (s[i] == ‘)’) { if (s[i – 1] == ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s[i – dp[i – 1] – 1] == ‘(‘) { dp[i] = dp[i – 1] + 2 + ((i – dp[i – 1] – 2 >= 0) ? dp[i – dp[i – 1] – 2] : 0); } maxLength = (dp[i] > maxLength) ? dp[i] : maxLength; } } return maxLength;}int main() { char s[] = “)()())”; printf(“Longest Valid Parentheses Length: %d\n”, longestValidParentheses(s)); return 0;} 2. C++ #include <iostream>#include <vector>#include <string>using namespace std;int longestValidParentheses(string s) { int n = s.size(); vector<int> dp(n, 0); int maxLength = 0; for (int i = 1; i < n; i++) { if (s[i] == ‘)’) { if (s[i – 1] == ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s[i – dp[i – 1] – 1] == ‘(‘) { dp[i] = dp[i – 1] + 2 + ((i – dp[i – 1] – 2 >= 0) ? dp[i – dp[i – 1] – 2] : 0); } maxLength = max(maxLength, dp[i]); } } return maxLength;}int main() { string s = “)()())”; cout << “Longest Valid Parentheses Length: ” << longestValidParentheses(s) << endl; return 0;} 3. Java public class LongestValidParentheses { public static int longestValidParentheses(String s) { int n = s.length(); int[] dp = new int[n]; int maxLength = 0; for (int i = 1; i < n; i++) { if (s.charAt(i) == ‘)’) { if (s.charAt(i – 1) == ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s.charAt(i – dp[i – 1] – 1) == ‘(‘) { dp[i] = dp[i – 1] + 2 + ((i – dp[i – 1] – 2 >= 0) ? dp[i – dp[i – 1] – 2] : 0); } maxLength = Math.max(maxLength, dp[i]); } } return maxLength; } public static void main(String[] args) { String s = “)()())”; System.out.println(“Longest Valid Parentheses Length: ” + longestValidParentheses(s)); }} 4. Python def longestValidParentheses(s: str) -> int: n = len(s) dp = [0] * n max_length = 0 for i in range(1, n): if s[i] == ‘)’: if s[i – 1] == ‘(‘: dp[i] = dp[i – 2] + 2 if i – 2 >= 0 else 2 elif i – dp[i – 1] – 1 >= 0 and s[i – dp[i – 1] – 1] == ‘(‘: dp[i] = dp[i – 1] + 2 + (dp[i – dp[i – 1] – 2] if i – dp[i – 1] – 2 >= 0 else 0) max_length = max(max_length, dp[i]) return max_length# Example usages = “)()())”print(f”Longest Valid Parentheses Length: {longestValidParentheses(s)}”) 5. C# using System;public class Solution { public int LongestValidParentheses(string s) { int n = s.Length; int[] dp = new int[n]; int maxLength = 0; for (int i = 1; i < n; i++) { if (s[i] == ‘)’) { if (s[i – 1] == ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s[i – dp[i – 1] – 1] == ‘(‘) { dp[i] = dp[i – 1] + 2 + ((i – dp[i – 1] – 2 >= 0) ? dp[i – dp[i – 1] – 2] : 0); } maxLength = Math.Max(maxLength, dp[i]); } } return maxLength; } public static void Main(string[] args) { Solution solution = new Solution(); string s = “)()())”; Console.WriteLine($”Longest Valid Parentheses Length: {solution.LongestValidParentheses(s)}”); }} 6. JavaScript var longestValidParentheses = function(s) { const n = s.length; const dp = Array(n).fill(0); let maxLength = 0; for (let i = 1; i < n; i++) { if (s[i] === ‘)’) { if (s[i – 1] === ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s[i – dp[i – 1] – 1] === ‘(‘) { dp[i] = dp[i – 1] + 2 + (i – dp[i – 1] – 2 >= 0 ? dp[i – dp[i – 1] – 2] : 0); } maxLength = Math.max(maxLength, dp[i]); } } return maxLength;};// Example usageconst s = “)()())”;console.log(“Longest Valid Parentheses Length:”, longestValidParentheses(s)); Summary:

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)