DSA

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:

Problem Statement: Given a string, determine if it represents a valid number. A valid number can be any of the following: The string may contain leading or trailing whitespace characters, and may include a decimal point and an exponent (denoted by e or E). Input: Output: Example 1: Input: “123”Output: true Example 2: Input: “3.14159”Output: true Example 3: Input: “1e10″Output: true Example 4: Input: “abc”Output: false Example 5: Input: “1e”Output: false Approach: The problem can be solved using state machine or regular expressions. The state machine is preferred here due to better control over transitions. Steps: Time Complexity: Code Implementation: 1. C: #include <stdio.h>#include <ctype.h>#include <stdbool.h>bool isNumber(char* s) { if (s == NULL) return false; int i = 0, n = 0; // Trim leading whitespace while (s[i] == ‘ ‘) i++; // Handle optional sign if (s[i] == ‘+’ || s[i] == ‘-‘) i++; bool numSeen = false, dotSeen = false, eSeen = false; // Process each character while (s[i] != ‘\0’) { if (isdigit(s[i])) { numSeen = true; } else if (s[i] == ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (s[i] == ‘e’ || s[i] == ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (s[i] == ‘+’ || s[i] == ‘-‘) { if (s[i – 1] != ‘e’ && s[i – 1] != ‘E’) return false; } else { return false; // Invalid character } i++; } return numSeen;}int main() { char s[] = “3.14159”; if (isNumber(s)) { printf(“Valid Number\n”); } else { printf(“Invalid Number\n”); } return 0;} 2. C++: #include <iostream>#include <string>#include <cctype>using namespace std;bool isNumber(string s) { int i = 0, n = s.length(); // Trim leading spaces while (i < n && s[i] == ‘ ‘) i++; if (i == n) return false; bool numSeen = false, dotSeen = false, eSeen = false; // Check each character while (i < n) { if (isdigit(s[i])) { numSeen = true; } else if (s[i] == ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (s[i] == ‘e’ || s[i] == ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (s[i] == ‘+’ || s[i] == ‘-‘) { if (s[i – 1] != ‘e’ && s[i – 1] != ‘E’) return false; } else { return false; } i++; } return numSeen;}int main() { string s = “3.14”; if (isNumber(s)) { cout << “Valid Number” << endl; } else { cout << “Invalid Number” << endl; } return 0;} 3. Java: public class ValidNumber { public static boolean isNumber(String s) { s = s.trim(); int n = s.length(); if (n == 0) return false; boolean numSeen = false, dotSeen = false, eSeen = false; for (int i = 0; i < n; i++) { char c = s.charAt(i); if (Character.isDigit(c)) { numSeen = true; } else if (c == ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (c == ‘e’ || c == ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (c == ‘+’ || c == ‘-‘) { if (i > 0 && s.charAt(i – 1) != ‘e’ && s.charAt(i – 1) != ‘E’) return false; } else { return false; } } return numSeen; } public static void main(String[] args) { String s = “3.14”; System.out.println(isNumber(s) ? “Valid Number” : “Invalid Number”); }} 4. Python: def isNumber(s: str) -> bool: s = s.strip() if not s: return False num_seen, dot_seen, e_seen = False, False, False for i in range(len(s)): char = s[i] if char.isdigit(): num_seen = True elif char == ‘.’: if dot_seen or e_seen: return False dot_seen = True elif char == ‘e’ or char == ‘E’: if e_seen or not num_seen: return False e_seen = True num_seen = False # Reset numSeen after exponent elif char == ‘+’ or char == ‘-‘: if i > 0 and s[i-1] not in (‘e’, ‘E’): return False else: return False return num_seen# Example Usages = “3.14”print(“Valid Number” if isNumber(s) else “Invalid Number”) 5. C#: using System;public class Solution { public bool IsNumber(string s) { s = s.Trim(); if (string.IsNullOrEmpty(s)) return false; bool numSeen = false, dotSeen = false, eSeen = false; for (int i = 0; i < s.Length; i++) { char c = s[i]; if (Char.IsDigit(c)) { numSeen = true; } else if (c == ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (c == ‘e’ || c == ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (c == ‘+’ || c == ‘-‘) { if (i > 0 && s[i – 1] != ‘e’ && s[i – 1] != ‘E’) return false; } else { return false; } } return numSeen; } public static void Main() { Solution solution = new Solution(); string s = “3.14”; Console.WriteLine(solution.IsNumber(s) ? “Valid Number” : “Invalid Number”); }} 6. JavaScript: function isNumber(s) { s = s.trim(); if (s.length === 0) return false; let numSeen = false, dotSeen = false, eSeen = false; for (let i = 0; i < s.length; i++) { let char = s[i]; if (/\d/.test(char)) { numSeen = true; } else if (char === ‘.’) { if (dotSeen || eSeen) return false; dotSeen = true; } else if (char === ‘e’ || char === ‘E’) { if (eSeen || !numSeen) return false; eSeen = true; numSeen = false; // Reset numSeen after exponent } else if (char === ‘+’ || char === ‘-‘) { if (i > 0 && (s[i-1] !== ‘e’ && s[i-1] !== ‘E’)) return false; } else { return false; } } return numSeen;}// Example Usagelet s = “3.14”;console.log(isNumber(s) ? “Valid Number” : “Invalid Number”); Summary:

The “Length of Last Word“ problem is a classic problem often asked in coding interviews. The task is to determine the length of the last word in a given string. A word is defined as a sequence of non-space characters, and the words in the string are separated by spaces. Problem Statement: Given a string s, return the length of the last word in it. Example: Input: “Hello World” Output: 5 Explanation: The last word is “World”, and its length is 5. Input: arduinoCopy code” fly me to the moon ” Output: 4 Explanation: The last word is “moon”, and its length is 4. Input: “luffy is still joyboy” Output: 6 Explanation: The last word is “joyboy”, and its length is 6. Approach: We can solve this problem in two main ways: Solution Approach 1: Iteration from the end Solution Approach 2: Using built-in functions (trim, split) Code Implementations: 1. C++ #include <iostream>#include <string>#include <algorithm>using namespace std;int lengthOfLastWord(string s) { int n = s.length(); int length = 0; // Start from the end of the string int i = n – 1; // Skip trailing spaces while (i >= 0 && s[i] == ‘ ‘) { i–; } // Count the length of the last word while (i >= 0 && s[i] != ‘ ‘) { length++; i–; } return length;}int main() { string str = “Hello World”; cout << “Length of last word: ” << lengthOfLastWord(str) << endl; // Output: 5 return 0;} 2. C #include <stdio.h>#include <string.h>int lengthOfLastWord(char *s) { int len = strlen(s); int length = 0; // Skip trailing spaces while (len > 0 && s[len – 1] == ‘ ‘) { len–; } // Count the length of the last word while (len > 0 && s[len – 1] != ‘ ‘) { length++; len–; } return length;}int main() { char str[] = “Hello World”; printf(“Length of last word: %d\n”, lengthOfLastWord(str)); // Output: 5 return 0;} 3. Java public class LengthOfLastWord { public int lengthOfLastWord(String s) { int length = 0; int n = s.length(); // Skip trailing spaces int i = n – 1; while (i >= 0 && s.charAt(i) == ‘ ‘) { i–; } // Count the length of the last word while (i >= 0 && s.charAt(i) != ‘ ‘) { length++; i–; } return length; } public static void main(String[] args) { LengthOfLastWord solution = new LengthOfLastWord(); String str = “Hello World”; System.out.println(“Length of last word: ” + solution.lengthOfLastWord(str)); // Output: 5 }} 4. Python def lengthOfLastWord(s: str) -> int: s = s.strip() # Remove leading/trailing spaces words = s.split() # Split the string into words return len(words[-1]) # Return the length of the last word# Test the functionprint(lengthOfLastWord(“Hello World”)) # Output: 5 5. C# using System;public class Solution { public int LengthOfLastWord(string s) { s = s.Trim(); // Remove leading/trailing spaces string[] words = s.Split(); // Split the string into words return words[words.Length – 1].Length; // Return the length of the last word } public static void Main() { Solution solution = new Solution(); string str = “Hello World”; Console.WriteLine(solution.LengthOfLastWord(str)); // Output: 5 }} 6. JavaScript function lengthOfLastWord(s) { s = s.trim(); // Remove leading/trailing spaces const words = s.split(‘ ‘); // Split the string into words return words[words.length – 1].length; // Return the length of the last word}// Test the functionconsole.log(lengthOfLastWord(“Hello World”)); // Output: 5 Time Complexity: Space Complexity: Summary: The “Length of Last Word” problem can be solved using either an iterative approach from the end of the string or by trimming and splitting the string. Both approaches have a time complexity of O(n), but the iterative approach can be more space-efficient, using O(1) extra space.