SkylineWebZ

Problem: Word Ladder II Problem Statement: Given two words, beginWord and endWord, and a dictionary wordList, find all shortest transformation sequences from beginWord to endWord, such that: Example 1: Input: beginWord = “hit”endWord = “cog”wordList = [“hot”, “dot”, “dog”, “lot”, “log”, “cog”] Output: [[“hit”, “hot”, “dot”, “dog”, “cog”], [“hit”, “hot”, “lot”, “log”, “cog”]] Example 2: Input: beginWord = “hit”endWord = “cog”wordList = [“hot”, “dot”, “dog”, “lot”, “log”] Output: [] Explanation: There is no possible transformation sequence from hit to cog because the word cog is not in the word list. Approach: The problem is essentially about finding the shortest paths in an unweighted graph, where each word is a node, and an edge exists between two nodes if one can be obtained by changing exactly one character. We can break the solution down into two major steps: Step 1: Breadth-First Search (BFS) Step 2: Backtracking Time Complexity: Algorithm: Code Implementation: 1. Python Code from collections import deque, defaultdictdef findLadders(beginWord, endWord, wordList): # Step 1: Edge case – If endWord is not in wordList, return an empty list. if endWord not in wordList: return [] # Step 2: Build a dictionary of all possible intermediate words wordList.add(beginWord) neighbors = defaultdict(list) for word in wordList: for i in range(len(word)): pattern = word[:i] + ‘*’ + word[i+1:] neighbors[pattern].append(word) # Step 3: BFS to find the shortest path length level = {beginWord: [[beginWord]]} # Map to keep track of paths queue = deque([beginWord]) found = False while queue and not found: visited = set() # Keep track of words visited in this level for _ in range(len(queue)): word = queue.popleft() for i in range(len(word)): pattern = word[:i] + ‘*’ + word[i+1:] for neighbor in neighbors[pattern]: if neighbor not in level: level[neighbor] = [] if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # Add the new word to all the possible paths if neighbor == endWord: found = True for path in level[word]: level[neighbor].append(path + [neighbor]) # Move to the next level, after exploring all nodes for the current level for word in visited: level[word] = [path for path in level[word] if path[-1] == word] # Step 4: Return the result return level[endWord]# Example test casebeginWord = “hit”endWord = “cog”wordList = {“hot”, “dot”, “dog”, “lot”, “log”, “cog”}result = findLadders(beginWord, endWord, wordList)print(result) Explanation of the Python Code: 2. C++ Code #include <iostream>#include <vector>#include <unordered_set>#include <unordered_map>#include <queue>#include <string>using namespace std;vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string>& wordList) { vector<vector<string>> result; if (wordList.find(endWord) == wordList.end()) return result; unordered_map<string, vector<vector<string>>> level; // to store the paths at each level unordered_set<string> currentLevel, nextLevel; currentLevel.insert(beginWord); wordList.insert(endWord); bool found = false; while (!currentLevel.empty() && !found) { for (auto& word : currentLevel) wordList.erase(word); // Remove words at this level nextLevel.clear(); for (auto& word : currentLevel) { string temp = word; for (int i = 0; i < word.length(); i++) { char original = temp[i]; temp[i] = ‘*’; // Replace character with * for (auto& neighbor : wordList) { if (neighbor == temp) { if (neighbor == endWord) found = true; for (auto& path : level[word]) { level[neighbor].push_back(path); } nextLevel.insert(neighbor); } } temp[i] = original; } } currentLevel.swap(nextLevel); } for (auto& path : level[endWord]) { result.push_back(path); } return result;}int main() { string beginWord = “hit”, endWord = “cog”; unordered_set<string> wordList = {“hot”, “dot”, “dog”, “lot”, “log”, “cog”}; vector<vector<string>> result = findLadders(beginWord, endWord, wordList); for (const auto& path : result) { for (const auto& word : path) { cout << word << ” “; } cout << endl; } return 0;} Explanation of C++ Code: 3. Java Code import java.util.*;public class WordLadderII { public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { List<List<String>> result = new ArrayList<>(); if (!wordList.contains(endWord)) return result; Map<String, List<List<String>>> level = new HashMap<>(); Set<String> currentLevel = new HashSet<>(); Set<String> nextLevel = new HashSet<>(); currentLevel.add(beginWord); wordList.add(endWord); boolean found = false; while (!currentLevel.isEmpty() && !found) { for (String word : currentLevel) wordList.remove(word); // Remove words at this level nextLevel.clear(); for (String word : currentLevel) { char[] temp = word.toCharArray(); for (int i = 0; i < temp.length; i++) { char original = temp[i]; temp[i] = ‘*’; // Replace character with * String pattern = new String(temp); if (wordList.contains(pattern)) { if (pattern.equals(endWord)) found = true; for (List<String> path : level.getOrDefault(word, new ArrayList<>())) { List<String> newPath = new ArrayList<>(path); newPath.add(pattern); level.computeIfAbsent(pattern, k -> new ArrayList<>()).add(newPath); } nextLevel.add(pattern); } temp[i] = original; // Restore original character } } currentLevel = nextLevel; } return level.getOrDefault(endWord, new ArrayList<>()); } public static void main(String[] args) { WordLadderII wl = new WordLadderII(); Set<String> wordList = new HashSet<>(Arrays.asList(“hot”, “dot”, “dog”, “lot”, “log”, “cog”)); List<List<String>> result = wl.findLadders(“hit”, “cog”, wordList); for (List<String> path : result) { System.out.println(path); } }} Explanation of Java Code: C Code #include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>#include <ctype.h>#include <limits.h>#define MAX_WORDS 1000#define WORD_LENGTH 10typedef struct Node { char word[WORD_LENGTH]; struct Node* next;} Node;typedef struct Queue { Node* front; Node* rear;} Queue;Queue* createQueue() { Queue* queue = (Queue*)malloc(sizeof(Queue)); queue->front = queue->rear = NULL; return queue;}void enqueue(Queue* queue, char* word) { Node* temp = (Node*)malloc(sizeof(Node)); strcpy(temp->word, word); temp->next = NULL; if (queue->rear) { queue->rear->next = temp; } else { queue->front = temp; } queue->rear = temp;}char* dequeue(Queue* queue) { if (queue->front == NULL) return NULL; Node* temp = queue->front; queue->front = queue->front->next; if (queue->front == NULL) { queue->rear = NULL; } char* word = temp->word; free(temp); return word;}bool isAdjacent(char* word1, char* word2) { int diff = 0; for (int i = 0; word1[i] != ‘\0’; i++) { if (word1[i] != word2[i]) { diff++; } if (diff > 1) return false; } return diff == 1;}void findLadders(char* beginWord, char* endWord, char* wordList[], int wordCount) { // BFS approach to find shortest paths Queue* queue = createQueue(); enqueue(queue, beginWord); while (queue->front != NULL) { char* current = dequeue(queue); // If current word is endWord, stop and print the path if (strcmp(current, endWord) == 0) { printf(“Found transformation sequence\n”); return; } for (int i = 0; i < wordCount; i++) { if (isAdjacent(current, wordList[i])) { enqueue(queue, wordList[i]); } } } printf(“No transformation found\n”);}int main() { char* wordList[] = {“hot”, “dot”, “dog”, “lot”, “log”, “cog”}; int wordCount

How many Subsets are possible for an Array of size ‘N’ ? Can we see a relationship of any sort between array N’s size and the number of subgroups it forms before diving into the solution? Yes, there is a relationship, as indicated by the following formula: An array of size N = 2^N has how many subsets? Proof: We have two options for each array element: Option 1: Add it to the subset.Option 2: Take it out of the subset.Total subsets = 2^N since each element has two options for contributing to the subset and there are N elements in total. Let’s examine how this observation can be used to build our solution. Printing all subsets using Backtracking To put the above concept into practice, take the actions listed below: C++ Java Python JavaScript Output 1 1 2 1 2 3 1 3 2 2 3 3 Complexity Analysis:

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.