SkylineWebZ

Problem Statement: Interleaving String Given three strings s1, s2, and s3, the task is to determine if s3 is formed by interleaving s1 and s2 while maintaining the relative order of characters from both strings s1 and s2. A string s3 is said to be an interleaving of s1 and s2 if: Example: Example 1: Example 2: Approach: The problem can be solved using Dynamic Programming (DP). The key idea is to use a 2D DP table where dp[i][j] represents whether the first i characters of s1 and the first j characters of s2 can form the first i+j characters of s3. Algorithm: Complexity: Code Implementations: 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 (strlen(s3) != m + n) return false; bool dp[m+1][n+1]; memset(dp, 0, 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-1][j]; } if (j > 0 && s2[j-1] == s3[i+j-1]) { 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 (s3.size() != m + n) 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-1][j]; } if (j > 0 && s2[j-1] == s3[i+j-1]) { 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\n”; } else { cout << “False\n”; } return 0;} Java: public class InterleavingString { public static boolean isInterleave(String s1, String s2, String s3) { int m = s1.length(), n = s2.length(); if (s3.length() != m + n) 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-1][j]; } if (j > 0 && s2.charAt(j-1) == s3.charAt(i+j-1)) { dp[i][j] |= dp[i][j-1]; } } } return dp[m][n]; } public static void main(String[] args) { String s1 = “abc”, s2 = “def”, s3 = “adbcef”; if (isInterleave(s1, s2, s3)) { System.out.println(“True”); } else { System.out.println(“False”); } }} Python: def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if len(s3) != m + n: 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 – 1][j] if j > 0 and s2[j – 1] == s3[i + j – 1]: dp[i][j] |= dp[i][j – 1] return dp[m][n]# Test cases1 = “abc”s2 = “def”s3 = “adbcef”print(isInterleave(s1, s2, s3)) # Output: True C#: using System;public class InterleavingString { public static bool IsInterleave(string s1, string s2, string s3) { int m = s1.Length, n = s2.Length; if (s3.Length != m + n) 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-1, j]; } if (j > 0 && s2[j-1] == s3[i+j-1]) { dp[i, j] |= dp[i, j-1]; } } } return dp[m, n]; } public static void Main() { string s1 = “abc”, s2 = “def”, s3 = “adbcef”; if (IsInterleave(s1, s2, s3)) { Console.WriteLine(“True”); } else { Console.WriteLine(“False”); } }} JavaScript: function isInterleave(s1, s2, s3) { let m = s1.length, n = s2.length; if (s3.length !== m + n) return false; let 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];}// Test caselet s1 = “abc”, s2 = “def”, s3 = “adbcef”;console.log(isInterleave(s1, s2, s3)); // Output: true Summary:

Problem Statement: Restore IP Addresses Given a string s containing only digits, restore it by returning all possible valid IP address combinations. A valid IP address consists of exactly four integers separated by periods (.), where each integer is between 0 and 255 (inclusive), and no integer has leading zeros unless it is “0”. Example 1: Input: s = “25525511135” Output: [“255.255.11.135”, “255.255.111.35”] Example 2: Input: s = “0000” Output: [“0.0.0.0”] Example 3: Input: s = “1111” Output: [“1.1.1.1″] Approach To solve this problem, we can use backtracking or depth-first search (DFS) to explore all possible valid IP address combinations. Each valid IP address consists of four parts, each part being a number between 0 and 255, and each part must not have leading zeros unless it is exactly “0”. Key Constraints: Plan: Time Complexity: Code Implementation C Code #include <stdio.h>#include <string.h>#include <stdlib.h>void backtrack(char *s, int start, int part, char *current, char **result, int *resultCount) { if (part == 4) { if (start == strlen(s)) { result[*resultCount] = strdup(current); (*resultCount)++; } return; } for (int len = 1; len <= 3; len++) { if (start + len > strlen(s)) break; char temp[len + 1]; strncpy(temp, s + start, len); temp[len] = ‘\0’; // Check validity of the segment if ((len == 1) || (temp[0] != ‘0’ && atoi(temp) <= 255)) { char nextCurrent[100]; snprintf(nextCurrent, sizeof(nextCurrent), “%s%s%s”, current, (part == 0 ? “” : “.”), temp); backtrack(s, start + len, part + 1, nextCurrent, result, resultCount); } }}char** restoreIpAddresses(char* s, int* returnSize) { char **result = (char **)malloc(100 * sizeof(char*)); *returnSize = 0; if (strlen(s) < 4 || strlen(s) > 12) return result; backtrack(s, 0, 0, “”, result, returnSize); return result;}int main() { char s[] = “25525511135”; int returnSize = 0; char **result = restoreIpAddresses(s, &returnSize); printf(“Possible IPs:\n”); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i]); free(result[i]); } free(result); return 0;} C++ Code #include <iostream>#include <vector>#include <string>using namespace std;void backtrack(string& s, int start, int part, string current, vector<string>& result) { if (part == 4) { if (start == s.size()) { result.push_back(current); } return; } for (int len = 1; len <= 3; len++) { if (start + len > s.size()) break; string temp = s.substr(start, len); // Check validity of the segment if ((len == 1) || (temp[0] != ‘0’ && stoi(temp) <= 255)) { backtrack(s, start + len, part + 1, current + (part == 0 ? “” : “.”) + temp, result); } }}vector<string> restoreIpAddresses(string s) { vector<string> result; if (s.size() < 4 || s.size() > 12) return result; backtrack(s, 0, 0, “”, result); return result;}int main() { string s = “25525511135”; vector<string> result = restoreIpAddresses(s); cout << “Possible IPs:” << endl; for (const string& ip : result) { cout << ip << endl; } return 0;} Java Code import java.util.ArrayList;import java.util.List;public class RestoreIPAddresses { private void backtrack(String s, int start, int part, String current, List<String> result) { if (part == 4) { if (start == s.length()) { result.add(current); } return; } for (int len = 1; len <= 3; len++) { if (start + len > s.length()) break; String temp = s.substring(start, start + len); // Check validity of the segment if ((len == 1) || (temp.charAt(0) != ‘0’ && Integer.parseInt(temp) <= 255)) { backtrack(s, start + len, part + 1, current + (part == 0 ? “” : “.”) + temp, result); } } } public List<String> restoreIpAddresses(String s) { List<String> result = new ArrayList<>(); if (s.length() < 4 || s.length() > 12) return result; backtrack(s, 0, 0, “”, result); return result; } public static void main(String[] args) { RestoreIPAddresses solution = new RestoreIPAddresses(); String s = “25525511135”; List<String> result = solution.restoreIpAddresses(s); System.out.println(“Possible IPs:”); for (String ip : result) { System.out.println(ip); } }} Python Code def restoreIpAddresses(s): result = [] def backtrack(start, part, current): if part == 4: if start == len(s): result.append(current) return for length in range(1, 4): if start + length > len(s): break temp = s[start:start + length] # Check validity of the segment if (length == 1) or (temp[0] != ‘0’ and int(temp) <= 255): backtrack(start + length, part + 1, current + (‘.’ if part > 0 else ”) + temp) if len(s) < 4 or len(s) > 12: return result backtrack(0, 0, “”) return result# Example usages = “25525511135”result = restoreIpAddresses(s)print(“Possible IPs:”)for ip in result: print(ip) C# Code using System;using System.Collections.Generic;public class RestoreIPAddresses{ private void Backtrack(string s, int start, int part, string current, List<string> result) { if (part == 4) { if (start == s.Length) { result.Add(current); } return; } for (int len = 1; len <= 3; len++) { if (start + len > s.Length) break; string temp = s.Substring(start, len); // Check validity of the segment if (len == 1 || (temp[0] != ‘0’ && int.Parse(temp) <= 255)) { Backtrack(s, start + len, part + 1, current + (part == 0 ? “” : “.”) + temp, result); } } } public List<string> RestoreIpAddresses(string s) { List<string> result = new List<string>(); if (s.Length < 4 || s.Length > 12) return result; Backtrack(s, 0, 0, “”, result); return result; } public static void Main() { string s = “25525511135”; RestoreIPAddresses solution = new RestoreIPAddresses(); var result = solution.RestoreIpAddresses(s); Console.WriteLine(“Possible IPs:”); foreach (var ip in result) { Console.WriteLine(ip); } }} JavaScript Code const restoreIpAddresses = (s) => { const result = []; const backtrack = (start, part, current) => { if (part === 4) { if (start === s.length) { result.push(current); } return; } for (let len = 1; len <= 3; len++) { if (start + len > s.length) break; const temp = s.slice(start, start + len); // Check validity of the segment if (len === 1 || (temp[0] !== ‘0’ && parseInt(temp) <= 255)) { backtrack(start + len, part + 1, current + (part === 0 ? “” : “.”) + temp); } } }; if (s.length < 4 || s.length > 12) return result; backtrack(0, 0, “”); return result;};// Example usageconst s = “25525511135”;const result = restoreIpAddresses(s);console.log(“Possible IPs:”);result.forEach(ip => console.log(ip)); Explanation: Time and

Problem Statement: Decode Ways Given a string s consisting of digits, return the total number of ways to decode it. A digit from 1 to 26 represents a letter from A to Z (i.e., ‘1’ -> ‘A’, ‘2’ -> ‘B’, …, ’26’ -> ‘Z’). For example: Note: Example 1: Input: s = “12” Output: 2 Explanation: The possible decodings are: Example 2: Input: s = “226” Output: 3 Explanation: The possible decodings are: Approach The problem can be solved using Dynamic Programming (DP). We will maintain a DP array where each entry dp[i] will represent the number of ways to decode the substring s[0..i-1]. Steps: Time Complexity: Code Implementations C Implementation #include <stdio.h>#include <string.h>int numDecodings(char* s) { int n = strlen(s); if (n == 0 || s[0] == ‘0’) return 0; int dp[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = 0; if (s[i – 1] != ‘0’) dp[i] += dp[i – 1]; // Single digit if (s[i – 2] == ‘1’ || (s[i – 2] == ‘2’ && s[i – 1] <= ‘6’)) { dp[i] += dp[i – 2]; // Two digits (10 to 26) } } return dp[n];}int main() { char s[] = “226”; printf(“Number of decodings: %d\n”, numDecodings(s)); return 0;} C++ Implementation #include <iostream>#include <vector>#include <string>using namespace std;int numDecodings(string s) { int n = s.size(); if (n == 0 || s[0] == ‘0’) return 0; vector<int> dp(n + 1, 0); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { if (s[i – 1] != ‘0’) dp[i] += dp[i – 1]; // Single digit if (s[i – 2] == ‘1’ || (s[i – 2] == ‘2’ && s[i – 1] <= ‘6’)) { dp[i] += dp[i – 2]; // Two digits (10 to 26) } } return dp[n];}int main() { string s = “226”; cout << “Number of decodings: ” << numDecodings(s) << endl; return 0;} Java Implementation public class DecodeWays { public static int numDecodings(String s) { int n = s.length(); if (n == 0 || s.charAt(0) == ‘0’) return 0; int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = 0; if (s.charAt(i – 1) != ‘0’) dp[i] += dp[i – 1]; // Single digit if (s.charAt(i – 2) == ‘1’ || (s.charAt(i – 2) == ‘2’ && s.charAt(i – 1) <= ‘6’)) { dp[i] += dp[i – 2]; // Two digits (10 to 26) } } return dp[n]; } public static void main(String[] args) { String s = “226”; System.out.println(“Number of decodings: ” + numDecodings(s)); }} Python Implementation pythonCopy codedef numDecodings(s): n = len(s) if n == 0 or s[0] == ‘0’: return 0 dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): if s[i – 1] != ‘0’: dp[i] += dp[i – 1] # Single digit if s[i – 2] == ‘1’ or (s[i – 2] == ‘2’ and s[i – 1] <= ‘6’): dp[i] += dp[i – 2] # Two digits (10 to 26) return dp[n] # Example usage s = “226” print(“Number of decodings:”, numDecodings(s)) C# Implementation using System;public class DecodeWays{ public static int NumDecodings(string s) { int n = s.Length; if (n == 0 || s[0] == ‘0’) return 0; int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = 0; if (s[i – 1] != ‘0’) dp[i] += dp[i – 1]; // Single digit if (s[i – 2] == ‘1’ || (s[i – 2] == ‘2’ && s[i – 1] <= ‘6’)) { dp[i] += dp[i – 2]; // Two digits (10 to 26) } } return dp[n]; } public static void Main() { string s = “226”; Console.WriteLine(“Number of decodings: ” + NumDecodings(s)); }} JavaScript Implementation const numDecodings = (s) => { const n = s.length; if (n === 0 || s[0] === ‘0’) return 0; const dp = Array(n + 1).fill(0); dp[0] = 1; dp[1] = 1; for (let i = 2; i <= n; i++) { if (s[i – 1] !== ‘0’) dp[i] += dp[i – 1]; // Single digit if (s[i – 2] === ‘1’ || (s[i – 2] === ‘2’ && s[i – 1] <= ‘6’)) { dp[i] += dp[i – 2]; // Two digits (10 to 26) } } return dp[n];};// Example usageconst s = “226”;console.log(“Number of decodings:”, numDecodings(s)); Explanation: Time Complexity:

Problem Statement: Scramble String Given two strings s1 and s2, return true if s2 is a scrambled string of s1. A string is scrambled if we can divide the string into two non-empty substrings and recursively swap them (or not) to obtain the target string. Example 1: Input: s1 = “great”, s2 = “rgeat” Output: true Explanation: We can divide “great” into two substrings “gr” and “eat”, and swap them to get “rgeat”. Example 2: Input: s1 = “abcde”, s2 = “caebd” Output: false Approach We can solve this problem using Dynamic Programming (DP). The idea is to recursively check whether one string can be transformed into another by recursively swapping substrings. Approach: Time Complexity: C Code Implementation #include <stdio.h>#include <stdbool.h>#include <string.h>#define MAX 1000bool dp[MAX][MAX][MAX]; // Memoization table// Check if s1[0…len-1] and s2[0…len-1] are scrambled stringsbool isScramble(char* s1, char* s2, int len) { if (strcmp(s1, s2) == 0) return true; if (len <= 1) return false; int index = len * 26; // Store position for memoization if (dp[index][s1[0] – ‘a’][s2[0] – ‘a’]) return true; for (int i = 1; i < len; i++) { if ((isScramble(s1, s2, i) && isScramble(s1 + i, s2 + i, len – i)) || (isScramble(s1, s2 + len – i, i) && isScramble(s1 + i, s2, len – i))) { return true; } } dp[index][s1[0] – ‘a’][s2[0] – ‘a’] = false; return false;}int main() { char s1[] = “great”; char s2[] = “rgeat”; if (isScramble(s1, s2, strlen(s1))) { printf(“True\n”); } else { printf(“False\n”); } return 0;} C++ Code Implementation #include <iostream>#include <vector>#include <string>#include <unordered_map>using namespace std;unordered_map<string, bool> memo;bool isScramble(string s1, string s2) { if (s1 == s2) return true; if (s1.length() != s2.length()) return false; string key = s1 + “_” + s2; if (memo.count(key)) return memo[key]; int n = s1.length(); for (int i = 1; i < n; i++) { // Case 1: Don’t swap if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) { memo[key] = true; return true; } // Case 2: Swap if (isScramble(s1.substr(0, i), s2.substr(n – i)) && isScramble(s1.substr(i), s2.substr(0, n – i))) { memo[key] = true; return true; } } memo[key] = false; return false;}int main() { string s1 = “great”; string s2 = “rgeat”; if (isScramble(s1, s2)) { cout << “True” << endl; } else { cout << “False” << endl; } return 0;} Java Code Implementation javaCopy codeimport java.util.HashMap; import java.util.Map; public class ScrambleString { private static Map<String, Boolean> memo = new HashMap<>(); public static boolean isScramble(String s1, String s2) { if (s1.equals(s2)) return true; if (s1.length() != s2.length()) return false; String key = s1 + “_” + s2; if (memo.containsKey(key)) return memo.get(key); int n = s1.length(); for (int i = 1; i < n; i++) { // Case 1: Don’t swap if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) { memo.put(key, true); return true; } // Case 2: Swap if (isScramble(s1.substring(0, i), s2.substring(n – i)) && isScramble(s1.substring(i), s2.substring(0, n – i))) { memo.put(key, true); return true; } } memo.put(key, false); return false; } public static void main(String[] args) { String s1 = “great”; String s2 = “rgeat”; if (isScramble(s1, s2)) { System.out.println(“True”); } else { System.out.println(“False”); } } } Python Code Implementation def isScramble(s1, s2, memo={}): if s1 == s2: return True if len(s1) != len(s2): return False if (s1, s2) in memo: return memo[(s1, s2)] n = len(s1) for i in range(1, n): # Case 1: Don’t swap if isScramble(s1[:i], s2[:i], memo) and isScramble(s1[i:], s2[i:], memo): memo[(s1, s2)] = True return True # Case 2: Swap if isScramble(s1[:i], s2[-i:], memo) and isScramble(s1[i:], s2[:-i], memo): memo[(s1, s2)] = True return True memo[(s1, s2)] = False return False# Example usages1 = “great”s2 = “rgeat”print(isScramble(s1, s2)) # Output: True C# Code Implementation using System;using System.Collections.Generic;public class ScrambleString{ private static Dictionary<string, bool> memo = new Dictionary<string, bool>(); public static bool IsScramble(string s1, string s2) { if (s1 == s2) return true; if (s1.Length != s2.Length) return false; string key = s1 + “_” + s2; if (memo.ContainsKey(key)) return memo[key]; int n = s1.Length; for (int i = 1; i < n; i++) { // Case 1: Don’t swap if (IsScramble(s1.Substring(0, i), s2.Substring(0, i)) && IsScramble(s1.Substring(i), s2.Substring(i))) { memo[key] = true; return true; } // Case 2: Swap if (IsScramble(s1.Substring(0, i), s2.Substring(n – i)) && IsScramble(s1.Substring(i), s2.Substring(0, n – i))) { memo[key] = true; return true; } } memo[key] = false; return false; } public static void Main() { string s1 = “great”; string s2 = “rgeat”; if (IsScramble(s1, s2)) { Console.WriteLine(“True”); } else { Console.WriteLine(“False”); } }} JavaScript Code Implementation const isScramble = (s1, s2, memo = {}) => { if (s1 === s2) return true; if (s1.length !== s2.length) return false; const key = s1 + “_” + s2; if (memo[key] !== undefined) return memo[key]; const n = s1.length; for (let i = 1; i < n; i++) { // Case 1: Don’t swap if (isScramble(s1.slice(0, i), s2.slice(0, i), memo) && isScramble(s1.slice(i), s2.slice(i), memo)) { memo[key] = true; return true; } // Case 2: Swap if (isScramble(s1.slice(0, i), s2.slice(n – i), memo) && isScramble(s1.slice(i), s2.slice(0, n – i), memo)) { memo[key] = true; return true; } } memo[key] = false; return false;};// Example usageconst s1 = “great”;const s2 = “rgeat”;console.log(isScramble(s1, s2)); // Output: true Conclusion In all implementations, the core idea is to check recursively if a string can be scrambled into another string by splitting and possibly swapping substrings. Memoization is used to avoid redundant calculations and optimize the performance. The solution is implemented in C, C++, Java, Python, C#, and JavaScript to demonstrate the approach in multiple programming languages.

Problem Statement: Word Search Given an m x n board of characters and a string word, write a function to check if the word exists in the board. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example Example 1: Example 2: Example 3: Approach We can solve this problem using Depth First Search (DFS) to explore possible paths for the word. The idea is to start from each cell and check whether the word can be formed by exploring adjacent cells recursively. Steps: Time and Space Complexity Code Implementations 1. C++ #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: bool exist(vector<vector<char>>& board, string word) { if (board.empty() || word.empty()) return false; int m = board.size(), n = board[0].size(); vector<vector<bool>> visited(m, vector<bool>(n, false)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (dfs(board, word, i, j, 0, visited)) return true; } } return false; }private: bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index, vector<vector<bool>>& visited) { if (index == word.size()) return true; // All characters are found if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || visited[i][j] || board[i][j] != word[index]) { return false; } visited[i][j] = true; // Mark as visited // Explore in all four directions bool result = dfs(board, word, i + 1, j, index + 1, visited) || dfs(board, word, i – 1, j, index + 1, visited) || dfs(board, word, i, j + 1, index + 1, visited) || dfs(board, word, i, j – 1, index + 1, visited); visited[i][j] = false; // Unmark for backtracking return result; }};int main() { Solution sol; vector<vector<char>> board = { {‘A’,’B’,’C’,’E’}, {‘S’,’F’,’C’,’S’}, {‘A’,’D’,’E’,’E’} }; string word = “ABCCED”; cout << boolalpha << sol.exist(board, word) << endl; // Output: true return 0;} 2. Java public class Solution { public boolean exist(char[][] board, String word) { if (board == null || board.length == 0 || word == null || word.length() == 0) return false; int m = board.length, n = board[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (dfs(board, word, i, j, 0, visited)) return true; } } return false; } private boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) { if (index == word.length()) return true; // All characters found if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)) { return false; } visited[i][j] = true; // Mark as visited // Explore four directions boolean result = dfs(board, word, i + 1, j, index + 1, visited) || dfs(board, word, i – 1, j, index + 1, visited) || dfs(board, word, i, j + 1, index + 1, visited) || dfs(board, word, i, j – 1, index + 1, visited); visited[i][j] = false; // Unmark for backtracking return result; } public static void main(String[] args) { Solution sol = new Solution(); char[][] board = { {‘A’,’B’,’C’,’E’}, {‘S’,’F’,’C’,’S’}, {‘A’,’D’,’E’,’E’} }; String word = “ABCCED”; System.out.println(sol.exist(board, word)); // Output: true }} 3. Python class Solution: def exist(self, board, word): if not board or not word: return False m, n = len(board), len(board[0]) visited = [[False] * n for _ in range(m)] def dfs(i, j, index): if index == len(word): return True if i < 0 or j < 0 or i >= m or j >= n or visited[i][j] or board[i][j] != word[index]: return False visited[i][j] = True # Mark as visited # Explore all four directions result = (dfs(i + 1, j, index + 1) or dfs(i – 1, j, index + 1) or dfs(i, j + 1, index + 1) or dfs(i, j – 1, index + 1)) visited[i][j] = False # Unmark for backtracking return result for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False# Example usageboard = [ [‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’]]word = “ABCCED”sol = Solution()print(sol.exist(board, word)) # Output: True 4. C# public class Solution { public bool Exist(char[][] board, string word) { if (board == null || board.Length == 0 || word == null || word.Length == 0) return false; int m = board.Length, n = board[0].Length; bool[,] visited = new bool[m, n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (DFS(board, word, i, j, 0, visited)) return true; } } return false; } private bool DFS(char[][] board, string word, int i, int j, int index, bool[,] visited) { if (index == word.Length) return true; // All characters found if (i < 0 || j < 0 || i >= board.Length || j >= board[0].Length || visited[i, j] || board[i][j] != word[index]) { return false; } visited[i, j] = true; // Mark as visited // Explore all four directions bool result = DFS(board, word, i + 1, j, index + 1, visited) || DFS(board, word, i – 1, j, index + 1, visited) || DFS(board, word, i, j + 1, index + 1, visited) || DFS(board, word, i, j – 1, index + 1, visited); visited[i, j] = false; // Unmark for backtracking return result; }}class Program { static void Main() { var board = new char[][] { new char[] {‘A’,’B’,’C’,’E’}, new char[] {‘S’,’F’,’C’,’S’}, new char[] {‘A’,’D’,’E’,’E’} }; string word = “ABCCED”; var sol = new Solution(); Console.WriteLine(sol.Exist(board, word)); // Output: True }} 5. JavaScript var exist = function(board, word) { if (!board || !word) return false; const m = board.length, n = board[0].length; const visited = Array.from({ length: m }, () => Array(n).fill(false)); function dfs(i, j, index) { if (index === word.length) return true; if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] ||

Problem Statement: Minimum Window Substring Given two strings s and t, find the minimum window in s which contains all the characters of t (including duplicate characters). A window is defined as a substring of s, and the minimum window is the smallest substring that contains all characters of t in any order. If no such window exists, return an empty string. Example Example 1: Example 2: Example 3: Approach The problem can be efficiently solved using the sliding window technique along with a hashmap to track the character frequencies in the current window. Steps: Algorithm Time and Space Complexity Code Implementations 1. C++ #include <iostream>#include <unordered_map>#include <climits>using namespace std;string minWindow(string s, string t) { if (s.empty() || t.empty()) return “”; unordered_map<char, int> need, have; for (char c : t) need[c]++; int left = 0, right = 0, required = need.size(), formed = 0; int minLen = INT_MAX, minLeft = 0; while (right < s.size()) { char c = s[right]; have[c]++; if (have[c] == need[c]) formed++; while (left <= right && formed == required) { // Update the minimum window if necessary if (right – left + 1 < minLen) { minLen = right – left + 1; minLeft = left; } // Contract the window from the left have[s[left]]–; if (have[s[left]] < need[s[left]]) formed–; left++; } right++; } return minLen == INT_MAX ? “” : s.substr(minLeft, minLen);}int main() { string s = “ADOBECODEBANC”, t = “ABC”; cout << “Minimum Window Substring: ” << minWindow(s, t) << endl; return 0;} 2. Java import java.util.HashMap;public class MinWindowSubstring { public static String minWindow(String s, String t) { if (s == null || t == null || s.length() < t.length()) { return “”; } HashMap<Character, Integer> need = new HashMap<>(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); } HashMap<Character, Integer> have = new HashMap<>(); int left = 0, right = 0, required = need.size(), formed = 0; int minLen = Integer.MAX_VALUE, minLeft = 0; while (right < s.length()) { char c = s.charAt(right); have.put(c, have.getOrDefault(c, 0) + 1); if (have.get(c).equals(need.get(c))) { formed++; } while (left <= right && formed == required) { if (right – left + 1 < minLen) { minLen = right – left + 1; minLeft = left; } have.put(s.charAt(left), have.get(s.charAt(left)) – 1); if (have.get(s.charAt(left)) < need.get(s.charAt(left))) { formed–; } left++; } right++; } return minLen == Integer.MAX_VALUE ? “” : s.substring(minLeft, minLeft + minLen); } public static void main(String[] args) { String s = “ADOBECODEBANC”, t = “ABC”; System.out.println(“Minimum Window Substring: ” + minWindow(s, t)); }} 3. Python from collections import Counterdef minWindow(s, t): if not s or not t: return “” need = Counter(t) have = Counter() left, right = 0, 0 required = len(need) formed = 0 min_len = float(‘inf’) min_left = 0 while right < len(s): c = s[right] have[c] += 1 if have[c] == need[c]: formed += 1 while left <= right and formed == required: if right – left + 1 < min_len: min_len = right – left + 1 min_left = left have[s[left]] -= 1 if have[s[left]] < need[s[left]]: formed -= 1 left += 1 right += 1 return s[min_left:min_left + min_len] if min_len != float(‘inf’) else “”# Example usages = “ADOBECODEBANC”t = “ABC”print(“Minimum Window Substring:”, minWindow(s, t)) 4. C# using System;using System.Collections.Generic;public class MinWindowSubstring{ public static string MinWindow(string s, string t) { if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return “”; var need = new Dictionary<char, int>(); foreach (var c in t) { if (!need.ContainsKey(c)) need[c] = 0; need[c]++; } var have = new Dictionary<char, int>(); int left = 0, right = 0, required = need.Count, formed = 0; int minLen = int.MaxValue, minLeft = 0; while (right < s.Length) { char c = s[right]; if (!have.ContainsKey(c)) have[c] = 0; have[c]++; if (have[c] == need[c]) formed++; while (left <= right && formed == required) { if (right – left + 1 < minLen) { minLen = right – left + 1; minLeft = left; } have[s[left]]–; if (have[s[left]] < need[s[left]]) formed–; left++; } right++; } return minLen == int.MaxValue ? “” : s.Substring(minLeft, minLen); } public static void Main() { string s = “ADOBECODEBANC”, t = “ABC”; Console.WriteLine(“Minimum Window Substring: ” + MinWindow(s, t)); }} 5. JavaScript function minWindow(s, t) { if (!s || !t) return “”; const need = {}; const have = {}; for (let char of t) { need[char] = (need[char] || 0) + 1; } let left = 0, right = 0; let required = Object.keys(need).length; let formed = 0; let minLen = Infinity, minLeft = 0; while (right < s.length) { let c = s[right]; have[c] = (have[c] || 0) + 1; if (have[c] === need[c]) formed++; while (left <= right && formed === required) { if (right – left + 1 < minLen) { minLen = right – left + 1; minLeft = left; } have[s[left]]–; if (have[s[left]] < need[s[left]]) formed–; left++; } right++; } return minLen === Infinity ? “” : s.slice(minLeft, minLeft + minLen);}// Example usageconst s = “ADOBECODEBANC”, t = “ABC”;console.log(“Minimum Window Substring:”, minWindow(s, t)); Conclusion The Minimum Window Substring problem is efficiently solvable using the sliding window technique with two pointers. The algorithm iterates over the string while maintaining a count of characters and adjusting the window size dynamically. This approach ensures that we can solve the problem in linear time, O(n), where n is the length of string s.

Problem Statement: Edit Distance Edit Distance (also known as Levenshtein distance) is a measure of the difference between two strings. It is the minimum number of operations required to convert one string into another. The operations allowed are: The goal is to determine the minimum number of operations required to transform one string into another. Example Let’s consider the two strings: Step-by-Step Transformation: Thus, the minimum edit distance between “kitten” and “sitting” is 3. Approach & Algorithm (Dynamic Programming) The Dynamic Programming (DP) approach to solving the Edit Distance problem works by filling a 2D table where each cell represents the edit distance between two substrings. We fill this table iteratively, starting from the base cases where one string is empty, and then using previously computed values to compute the distances for larger substrings. Steps: Time and Space Complexity Code Implementations 1. C #include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int min(int a, int b, int c) { return std::min(std::min(a, b), c);}int editDistance(char *s1, char *s2) { int m = strlen(s1); int n = strlen(s2); int dp[m + 1][n + 1]; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0) dp[i][j] = j; else if (j == 0) dp[i][j] = i; else if (s1[i – 1] == s2[j – 1]) dp[i][j] = dp[i – 1][j – 1]; else dp[i][j] = min(dp[i – 1][j] + 1, dp[i][j – 1] + 1, dp[i – 1][j – 1] + 1); } } return dp[m][n];}int main() { char s1[] = “kitten”; char s2[] = “sitting”; printf(“Edit Distance: %d\n”, editDistance(s1, s2)); return 0;} 2. C++ #include <iostream>#include <vector>#include <algorithm>using namespace std;int editDistance(string s1, string s2) { int m = s1.size(); int n = s2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0) dp[i][j] = j; else if (j == 0) dp[i][j] = i; else if (s1[i – 1] == s2[j – 1]) dp[i][j] = dp[i – 1][j – 1]; else dp[i][j] = min({dp[i – 1][j] + 1, dp[i][j – 1] + 1, dp[i – 1][j – 1] + 1}); } } return dp[m][n];}int main() { string s1 = “kitten”, s2 = “sitting”; cout << “Edit Distance: ” << editDistance(s1, s2) << endl; return 0;} 3. Java public class EditDistance { public static int min(int a, int b, int c) { return Math.min(Math.min(a, b), c); } public static int editDistance(String s1, String s2) { int m = s1.length(); int n = s2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0) dp[i][j] = j; else if (j == 0) dp[i][j] = i; else if (s1.charAt(i – 1) == s2.charAt(j – 1)) dp[i][j] = dp[i – 1][j – 1]; else dp[i][j] = min(dp[i – 1][j] + 1, dp[i][j – 1] + 1, dp[i – 1][j – 1] + 1); } } return dp[m][n]; } public static void main(String[] args) { String s1 = “kitten”, s2 = “sitting”; System.out.println(“Edit Distance: ” + editDistance(s1, s2)); }} 4. Python def edit_distance(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if i == 0: dp[i][j] = j elif j == 0: dp[i][j] = i elif s1[i – 1] == s2[j – 1]: dp[i][j] = dp[i – 1][j – 1] else: dp[i][j] = min(dp[i – 1][j] + 1, dp[i][j – 1] + 1, dp[i – 1][j – 1] + 1) return dp[m][n]# Example usages1 = “kitten”s2 = “sitting”print(“Edit Distance:”, edit_distance(s1, s2)) 5. C# using System;public class EditDistance{ public static int Min(int a, int b, int c) { return Math.Min(Math.Min(a, b), c); } public static int EditDistanceAlgorithm(string s1, string s2) { int m = s1.Length, n = s2.Length; int[,] dp = new int[m + 1, n + 1]; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0) dp[i, j] = j; else if (j == 0) dp[i, j] = i; else if (s1[i – 1] == s2[j – 1]) dp[i, j] = dp[i – 1, j – 1]; else dp[i, j] = Min(dp[i – 1, j] + 1, dp[i, j – 1] + 1, dp[i – 1, j – 1] + 1); } } return dp[m, n]; } public static void Main() { string s1 = “kitten”, s2 = “sitting”; Console.WriteLine(“Edit Distance: ” + EditDistanceAlgorithm(s1, s2)); }} 6. JavaScript function editDistance(s1, s2) { const m = s1.length, n = s2.length; const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { if (i === 0) dp[i][j] = j; else if (j === 0) dp[i][j] = i; else if (s1[i – 1] === s2[j – 1]) dp[i][j] = dp[i – 1][j – 1]; else dp[i][j] = Math.min(dp[i – 1][j] + 1, dp[i][j – 1] + 1, dp[i – 1][j – 1] + 1); } } return dp[m][n];}// Example usageconst s1 = “kitten”, s2 = “sitting”;console.log(“Edit Distance:”, editDistance(s1, s2)); Conclusion The Edit Distance problem is a classical example of dynamic programming. The time and space complexities are quadratic in terms of the lengths of the two strings. By using a 2D DP table, we can solve this problem efficiently for reasonably sized strings.

Problem Statement: Simplify Path You are given an absolute path for a file or directory in a Unix-style file system, where the path starts with a / (root directory) and can contain several subdirectories separated by /. The task is to simplify the given path by eliminating redundant parts and returning the canonical (simplified) path. Rules: Example: Input: “/home/../usr/./bin” Output: “/usr/bin” Explanation: Approach: Time Complexity: Space Complexity: Code Implementations: 1. C #include <stdio.h>#include <stdlib.h>#include <string.h>char* simplifyPath(char* path) { char* result = (char*)malloc(sizeof(char) * (strlen(path) + 1)); char* stack[1000]; int top = -1; // Split the path by ‘/’ char* token = strtok(path, “/”); while (token != NULL) { if (strcmp(token, “.”) == 0 || strlen(token) == 0) { // Skip current directory and empty strings } else if (strcmp(token, “..”) == 0) { // Pop from stack (go up one directory) if (top >= 0) { top–; } } else { // Push directory to stack stack[++top] = token; } token = strtok(NULL, “/”); } // Rebuild the path if (top == -1) { result[0] = ‘/’; result[1] = ‘\0’; return result; } int index = 0; for (int i = 0; i <= top; i++) { result[index++] = ‘/’; strcpy(result + index, stack[i]); index += strlen(stack[i]); } result[index] = ‘\0’; return result;}int main() { char path[] = “/home/../usr/./bin”; char* simplifiedPath = simplifyPath(path); printf(“Simplified Path: %s\n”, simplifiedPath); free(simplifiedPath); return 0;} 2. C++ #include <iostream>#include <sstream>#include <vector>#include <string>using namespace std;string simplifyPath(string path) { vector<string> stack; stringstream ss(path); string token; // Split the path by ‘/’ while (getline(ss, token, ‘/’)) { if (token == “” || token == “.”) { // Skip empty strings and current directory } else if (token == “..”) { // Move up one directory if (!stack.empty()) { stack.pop_back(); } } else { // Push directory to stack stack.push_back(token); } } // Rebuild the path if (stack.empty()) return “/”; string result = “”; for (const string& dir : stack) { result += “/” + dir; } return result;}int main() { string path = “/home/../usr/./bin”; cout << “Simplified Path: ” << simplifyPath(path) << endl; return 0;} 3. Java import java.util.*;public class Solution { public String simplifyPath(String path) { Deque<String> stack = new LinkedList<>(); String[] components = path.split(“/”); for (String component : components) { if (component.equals(“”) || component.equals(“.”)) { // Skip empty or current directory } else if (component.equals(“..”)) { // Pop from stack (go up one directory) if (!stack.isEmpty()) { stack.pollLast(); } } else { // Push directory to stack stack.offerLast(component); } } if (stack.isEmpty()) { return “/”; } // Rebuild the path StringBuilder result = new StringBuilder(); for (String dir : stack) { result.append(“/”).append(dir); } return result.toString(); } public static void main(String[] args) { Solution sol = new Solution(); String path = “/home/../usr/./bin”; System.out.println(“Simplified Path: ” + sol.simplifyPath(path)); }} 4. Python def simplifyPath(path: str) -> str: stack = [] components = path.split(“/”) for component in components: if component == “” or component == “.”: # Skip empty or current directory continue elif component == “..”: # Move up one directory if stack: stack.pop() else: # Push directory to stack stack.append(component) # Rebuild the path return “/” + “/”.join(stack) if stack else “/”# Testpath = “/home/../usr/./bin”print(“Simplified Path:”, simplifyPath(path)) 5. C# using System;using System.Collections.Generic;public class Solution { public string SimplifyPath(string path) { Stack<string> stack = new Stack<string>(); string[] components = path.Split(‘/’); foreach (var component in components) { if (component == “” || component == “.”) { // Skip empty or current directory continue; } else if (component == “..”) { // Pop from stack (go up one directory) if (stack.Count > 0) { stack.Pop(); } } else { // Push directory to stack stack.Push(component); } } if (stack.Count == 0) { return “/”; } // Rebuild the path List<string> result = new List<string>(); while (stack.Count > 0) { result.Insert(0, stack.Pop()); } return “/” + string.Join(“/”, result); } public static void Main() { Solution sol = new Solution(); string path = “/home/../usr/./bin”; Console.WriteLine(“Simplified Path: ” + sol.SimplifyPath(path)); }} 6. JavaScript function simplifyPath(path) { const stack = []; const components = path.split(“/”); for (let component of components) { if (component === “” || component === “.”) { // Skip empty or current directory continue; } else if (component === “..”) { // Pop from stack (go up one directory) if (stack.length > 0) { stack.pop(); } } else { // Push directory to stack stack.push(component); } } // Rebuild the path return stack.length === 0 ? “/” : “/” + stack.join(“/”);}// Testlet path = “/home/../usr/./bin”;console.log(“Simplified Path:”, simplifyPath(path)); Summary: The algorithm involves splitting the input path into components and using a stack to simulate directory navigation. By processing each component, we can effectively simplify the path. This approach ensures that we handle edge cases like repeated slashes, . (current directory), and .. (parent directory) correctly.

Problem Statement: Text Justification You are given a list of words and a length maxWidth. Your task is to arrange the words in such a way that the text is fully justified. The goal is to make each line of text exactly maxWidth characters long. The rules for text justification are: Example: Input:words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]maxWidth = 16Output:[ “This is an”, “example of text”, “justification. “] Approach: To solve this problem, we need to build the lines word by word, ensuring that each line is fully justified. Here’s how we can do it step by step: Algorithm: Time Complexity: Space Complexity: Code Implementations: 1. C #include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>char** fullJustify(char** words, int wordsSize, int maxWidth, int* returnSize) { // Initialize return array char** result = (char**)malloc(sizeof(char*) * wordsSize); *returnSize = 0; int i = 0; while (i < wordsSize) { int j = i + 1; int lineLength = strlen(words[i]); // Add words to the current line while (j < wordsSize && lineLength + strlen(words[j]) + (j – i – 1) < maxWidth) { lineLength += strlen(words[j]); j++; } // Now we have words[i…j-1] in the current line int numWords = j – i; int numSpaces = maxWidth – lineLength; char* line = (char*)malloc(sizeof(char) * (maxWidth + 1)); int pos = 0; // If it’s a single word, just copy it if (numWords == 1) { strcpy(line, words[i]); pos += strlen(words[i]); while (pos < maxWidth) { line[pos++] = ‘ ‘; } } else { // Distribute spaces int evenSpace = numSpaces / (numWords – 1); int extraSpace = numSpaces % (numWords – 1); for (int k = i; k < j – 1; k++) { strcpy(&line[pos], words[k]); pos += strlen(words[k]); for (int s = 0; s < evenSpace; s++) { line[pos++] = ‘ ‘; } if (extraSpace > 0) { line[pos++] = ‘ ‘; extraSpace–; } } strcpy(&line[pos], words[j – 1]); pos += strlen(words[j – 1]); } line[pos] = ‘\0’; result[*returnSize] = line; (*returnSize)++; i = j; } return result;}int main() { char* words[] = {“This”, “is”, “an”, “example”, “of”, “text”, “justification.”}; int wordsSize = 7; int maxWidth = 16; int returnSize = 0; char** result = fullJustify(words, wordsSize, maxWidth, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“\”%s\”\n”, result[i]); free(result[i]); } free(result); return 0;} 2. C++ #include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;vector<string> fullJustify(vector<string>& words, int maxWidth) { vector<string> result; int n = words.size(); int i = 0; while (i < n) { int length = words[i].size(); int j = i + 1; // Fit as many words as possible in the current line while (j < n && length + words[j].size() + (j – i – 1) < maxWidth) { length += words[j].size(); j++; } int numWords = j – i; int numSpaces = maxWidth – length; string line = “”; // Single word case if (numWords == 1) { line = words[i]; while (line.size() < maxWidth) { line += ” “; } } else { int spacesPerGap = numSpaces / (numWords – 1); int extraSpaces = numSpaces % (numWords – 1); for (int k = i; k < j – 1; k++) { line += words[k]; line += string(spacesPerGap, ‘ ‘); if (extraSpaces– > 0) line += ” “; } line += words[j – 1]; } result.push_back(line); i = j; } return result;}int main() { vector<string> words = {“This”, “is”, “an”, “example”, “of”, “text”, “justification.”}; int maxWidth = 16; vector<string> result = fullJustify(words, maxWidth); for (const string& line : result) { cout << “\”” << line << “\”” << endl; } return 0;} 3. Java import java.util.*;public class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> result = new ArrayList<>(); int n = words.length; int i = 0; while (i < n) { int length = words[i].length(); int j = i + 1; // Fit as many words as possible in the current line while (j < n && length + words[j].length() + (j – i – 1) < maxWidth) { length += words[j].length(); j++; } int numWords = j – i; int numSpaces = maxWidth – length; StringBuilder line = new StringBuilder(); // Single word case if (numWords == 1) { line.append(words[i]); while (line.length() < maxWidth) { line.append(” “); } } else { int spacesPerGap = numSpaces / (numWords – 1); int extraSpaces = numSpaces % (numWords – 1); for (int k = i; k < j – 1; k++) { line.append(words[k]); for (int s = 0; s < spacesPerGap; s++) { line.append(” “); } if (extraSpaces > 0) { line.append(” “); extraSpaces–; } } line.append(words[j – 1]); } result.add(line.toString()); i = j; } return result; } public static void main(String[] args) { Solution solution = new Solution(); String[] words = {“This”, “is”, “an”, “example”, “of”, “text”, “justification.”}; int maxWidth = 16; List<String> result = solution.fullJustify(words, maxWidth); for (String line : result) { System.out.println(“\”” + line + “\””); } }} 4. Python def fullJustify(words, maxWidth): result = [] i = 0 while i < len(words): line_length = len(words[i]) j = i + 1 # Add words to the current line until the width is exceeded while j < len(words) and line_length + len(words[j]) + (j – i – 1) < maxWidth: line_length += len(words[j]) j += 1 # Calculate spaces num_words = j – i num_spaces = maxWidth – line_length line = “” # Single word case if num_words == 1: line = words[i] while len(line) < maxWidth: line += ” ” else: spaces_per_gap = num_spaces // (num_words – 1) extra_spaces = num_spaces % (num_words – 1) for k in range(i, j – 1): line += words[k] line += ” ” * spaces_per_gap if extra_spaces > 0: line += ” ” extra_spaces -= 1 line += words[j – 1] result.append(line) i = j return result# Testwords = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]maxWidth = 16result = fullJustify(words, maxWidth)for line in result: print(f”\”{line}\””) 5. C# using System;using System.Collections.Generic;using System.Text;class Solution { public IList<string> FullJustify(string[] words, int maxWidth) { List<string> result = new List<string>(); int

Problem Statement: You are given two binary strings, a and b. Each string represents a non-negative integer, where each character is either ‘0’ or ‘1’. You need to return their sum, also as a binary string. Example: Input:a = “1010” b = “1011”Output:”10101″ Approach: The problem can be solved by simulating the binary addition process, similar to how we add numbers by hand. We’ll start adding from the rightmost bit (the least significant bit) and move leftwards. We need to keep track of the carry that might result from the addition of two bits. Steps: Algorithm: Time Complexity: The time complexity is O(max(n, m)), where n and m are the lengths of the two binary strings a and b. We go through both strings at most once. Space Complexity: The space complexity is O(max(n, m)) due to the space used to store the result string. Code Implementations 1. C #include <stdio.h>#include <string.h>#include <stdlib.h>char* addBinary(char* a, char* b) { int i = strlen(a) – 1, j = strlen(b) – 1, carry = 0; int size = (i > j ? i : j) + 2; // Maximum length needed char* result = (char*)malloc(sizeof(char) * (size + 1)); int k = 0; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += a[i–] – ‘0’; if (j >= 0) sum += b[j–] – ‘0’; result[k++] = (sum % 2) + ‘0’; carry = sum / 2; } result[k] = ‘\0’; // Reverse the result string for (int start = 0, end = k – 1; start < end; start++, end–) { char temp = result[start]; result[start] = result[end]; result[end] = temp; } return result;}int main() { char a[] = “1010”, b[] = “1011”; char* result = addBinary(a, b); printf(“Sum: %s\n”, result); free(result); return 0;} 2. C++ #include <iostream>#include <string>using namespace std;string addBinary(string a, string b) { int i = a.length() – 1, j = b.length() – 1, carry = 0; string result = “”; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += a[i–] – ‘0’; if (j >= 0) sum += b[j–] – ‘0’; result = char(sum % 2 + ‘0’) + result; carry = sum / 2; } return result;}int main() { string a = “1010”, b = “1011”; cout << “Sum: ” << addBinary(a, b) << endl; return 0;} 3. Java public class Solution { public String addBinary(String a, String b) { int i = a.length() – 1, j = b.length() – 1, carry = 0; StringBuilder result = new StringBuilder(); while (i >= 0 || j >= 0 || carry != 0) { int sum = carry; if (i >= 0) sum += a.charAt(i–) – ‘0’; if (j >= 0) sum += b.charAt(j–) – ‘0’; result.append(sum % 2); carry = sum / 2; } return result.reverse().toString(); } public static void main(String[] args) { Solution sol = new Solution(); String a = “1010”, b = “1011”; System.out.println(“Sum: ” + sol.addBinary(a, b)); }} 4. Python def addBinary(a: str, b: str) -> str: i, j, carry = len(a) – 1, len(b) – 1, 0 result = [] while i >= 0 or j >= 0 or carry: sum = carry if i >= 0: sum += int(a[i]) i -= 1 if j >= 0: sum += int(b[j]) j -= 1 result.append(str(sum % 2)) carry = sum // 2 return ”.join(reversed(result))# Testa = “1010”b = “1011”print(“Sum:”, addBinary(a, b)) 5. C# using System;using System.Text;class Solution { public string AddBinary(string a, string b) { int i = a.Length – 1, j = b.Length – 1, carry = 0; StringBuilder result = new StringBuilder(); while (i >= 0 || j >= 0 || carry != 0) { int sum = carry; if (i >= 0) sum += a[i–] – ‘0’; if (j >= 0) sum += b[j–] – ‘0’; result.Append(sum % 2); carry = sum / 2; } char[] resultArr = result.ToString().ToCharArray(); Array.Reverse(resultArr); return new string(resultArr); } public static void Main() { Solution sol = new Solution(); string a = “1010”, b = “1011”; Console.WriteLine(“Sum: ” + sol.AddBinary(a, b)); }} 6. JavaScript function addBinary(a, b) { let i = a.length – 1, j = b.length – 1, carry = 0; let result = []; while (i >= 0 || j >= 0 || carry) { let sum = carry; if (i >= 0) sum += a[i–] – ‘0’; if (j >= 0) sum += b[j–] – ‘0’; result.push(sum % 2); carry = Math.floor(sum / 2); } return result.reverse().join(”);}// Testlet a = “1010”, b = “1011”;console.log(“Sum:”, addBinary(a, b)); Summary: