DSA

Storing the width of consecutive 1’s ending at every cell (i, j) in a 2D array is the aim. Beginning from every cell (i, j) with value 1, iterate upwards row by row, determine the minimal width of 1’s in the column to guarantee the rectangle stays valid. The minimal width multiplied by the height yields the size of the rectangle, which updates the maximum area found thus far. Initialize a 2D matrix memo of size nm to hold the width of successive 1s ending at every cell (i, j). Starting at 0 Go iteratively across every cell (i, j) in the input matrix. Should the value at (i, j) be 1, use these guidelines: Should j = 0, set memo[i][j] = 1; otherwise, set memo[i][j] = 1 + memo[i][j – 1]. Define width = memo[i][j]. Update width = min(width, memo[k][j] and get the rectangle area width(i – k + 1) for every row k from i to 0. Add to the maximum area discovered thus far.Get back the computed maximum area. C++ Java Python C# JavaScript Output 8

Finding the biggest size rectangle binary-sub-matrix with all 1’s from a 2d binary matrix mat[][] is the goal. Example Table of Content Time and O(m) Space Using Largest Rectangular Area in a Histogram ApproachThis method derives from the Largest Rectangular Area in a Histogram concept. The concept is to discover the largest size rectangle in the matrix by first treating every row as the basis of a histogram. The greatest area of the histogram can be obtained knowing the height of the bars. This allows one to discover the histogram’s largest area of bars in each row. Update the next row with the previous row and determine the greatest area under the histogram, so using each 1’s as filled squares and 0’s with an empty square and considering each row as the basis. Illustration:  C++ Java Python C# javaScript Output 8

The Word Break II problem extends the classic Word Break problem, where you need to not only determine if a string can be segmented into a sequence of dictionary words but also return all possible segmentations. Problem Statement: Given a string s and a dictionary of words wordDict, return all possible sentences formed by segmenting s into a space-separated sequence of one or more dictionary words. Example: Approach: The approach is similar to Word Break with dynamic programming, but this time we need to backtrack to construct all possible valid sentences. We will use: Steps: Code Implementations in Multiple Languages: 1. C Code: #include <stdio.h>#include <string.h>#include <stdbool.h>#include <stdlib.h>bool wordBreakUtil(char *s, int start, int end, bool *dp) { if (start == end) return true; if (dp[start]) return false; // If already visited, no need to check dp[start] = true; for (int i = start + 1; i <= end; i++) { char substr[i – start]; strncpy(substr, s + start, i – start); substr[i – start] = ‘\0’; if (strstr(wordDict, substr) != NULL && wordBreakUtil(s, i, end, dp)) { return true; } } return false;}int main() { char *s = “catsanddog”; char *wordDict[] = {“cat”, “cats”, “and”, “sand”, “dog”}; // Test all possible word breaks if (wordBreakUtil(s, 0, strlen(s), dp)) { printf(“Possible word breaks exist”); } else { printf(“Impossible word breaks”); } return 0;} 2. Python Code (Word Break II): def wordBreak(s, wordDict): # Convert wordDict to a set for fast lookup word_set = set(wordDict) # Memoization: cache the results for substrings memo = {} def backtrack(start): if start == len(s): return [”] # Reached the end, return an empty string to signify no more words if start in memo: return memo[start] # Return already computed result for this start index result = [] # Try all possible substrings starting from ‘start’ for end in range(start + 1, len(s) + 1): if s[start:end] in word_set: # If the substring is a valid word, backtrack to find the rest of the sentence rest_of_sentences = backtrack(end) for sentence in rest_of_sentences: # If rest_of_sentences is empty, just return the word itself result.append(s[start:end] + (” if not sentence else ‘ ‘ + sentence)) # Store the result in memoization cache and return it memo[start] = result return result return backtrack(0)# Test cases = “catsanddog”wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]print(wordBreak(s, wordDict)) # Output: [“cats and dog”, “cat sand dog”] Explanation: 3. C++ Code (Word Break II): #include <iostream>#include <vector>#include <unordered_set>#include <unordered_map>#include <string>using namespace std;class Solution {public: vector<string> wordBreak(string s, unordered_set<string>& wordDict) { unordered_map<int, vector<string>> memo; return backtrack(s, 0, wordDict, memo); }private: vector<string> backtrack(const string& s, int start, unordered_set<string>& wordDict, unordered_map<int, vector<string>>& memo) { if (start == s.length()) return {“”}; // Base case: reach the end of the string if (memo.find(start) != memo.end()) return memo[start]; // If already computed vector<string> result; // Try all possible substrings starting from ‘start’ for (int end = start + 1; end <= s.length(); end++) { string word = s.substr(start, end – start); if (wordDict.find(word) != wordDict.end()) { vector<string> restOfSentences = backtrack(s, end, wordDict, memo); for (string sentence : restOfSentences) { result.push_back(word + (sentence.empty() ? “” : ” ” + sentence)); } } } memo[start] = result; return result; }};int main() { Solution solution; unordered_set<string> wordDict = {“cat”, “cats”, “and”, “sand”, “dog”}; string s = “catsanddog”; vector<string> result = solution.wordBreak(s, wordDict); for (const string& sentence : result) { cout << sentence << endl; // Output: “cats and dog”, “cat sand dog” } return 0;} Explanation: 4. Java Code (Word Break II): import java.util.*;public class Solution { public List<String> wordBreak(String s, List<String> wordDict) { Set<String> wordSet = new HashSet<>(wordDict); Map<Integer, List<String>> memo = new HashMap<>(); return backtrack(s, 0, wordSet, memo); } private List<String> backtrack(String s, int start, Set<String> wordSet, Map<Integer, List<String>> memo) { if (start == s.length()) return Arrays.asList(“”); // Base case: end of string if (memo.containsKey(start)) return memo.get(start); // Return if already computed List<String> result = new ArrayList<>(); // Try all possible substrings starting from ‘start’ for (int end = start + 1; end <= s.length(); end++) { String word = s.substring(start, end); if (wordSet.contains(word)) { List<String> restOfSentences = backtrack(s, end, wordSet, memo); for (String sentence : restOfSentences) { result.add(word + (sentence.isEmpty() ? “” : ” ” + sentence)); } } } memo.put(start, result); // Memoize result for the current start index return result; } public static void main(String[] args) { Solution solution = new Solution(); List<String> wordDict = Arrays.asList(“cat”, “cats”, “and”, “sand”, “dog”); String s = “catsanddog”; List<String> result = solution.wordBreak(s, wordDict); for (String sentence : result) { System.out.println(sentence); // Output: “cats and dog”, “cat sand dog” } }} Explanation: 5. C# Code (Word Break II): using System;using System.Collections.Generic;public class Solution { public IList<string> WordBreak(string s, IList<string> wordDict) { HashSet<string> wordSet = new HashSet<string>(wordDict); Dictionary<int, List<string>> memo = new Dictionary<int, List<string>>(); return Backtrack(s, 0, wordSet, memo); } private List<string> Backtrack(string s, int start, HashSet<string> wordSet, Dictionary<int, List<string>> memo) { if (start == s.Length) return new List<string> { “” }; // Base case if (memo.ContainsKey(start)) return memo[start]; // Return if already computed List<string> result = new List<string>(); // Try all possible substrings starting from ‘start’ for (int end = start + 1; end <= s.Length; end++) { string word = s.Substring(start, end – start); if (wordSet.Contains(word)) { List<string> restOfSentences = Backtrack(s, end, wordSet, memo); foreach (string sentence in restOfSentences) { result.Add(word + (string.IsNullOrEmpty(sentence) ? “” : ” ” + sentence)); } } } memo[start] = result; // Memoize result for the current start index return result; } public static void Main() { Solution solution = new Solution(); IList<string> wordDict = new List<string> { “cat”, “cats”, “and”, “sand”, “dog” }; string s = “catsanddog”; IList<string> result = solution.WordBreak(s, wordDict); foreach (string sentence in result) { Console.WriteLine(sentence); // Output: “cats and dog”, “cat sand dog” } }} Explanation: 6. JavaScript Code (Word Break II): function wordBreak(s, wordDict) { const wordSet = new Set(wordDict); const memo = {}; function backtrack(start) { if (start === s.length) return [”]; // Base case: reached the end of the string if (memo[start]) return memo[start]; // If already computed

The Word Break problem involves determining if a given string can be segmented into a sequence of valid words from a dictionary. This is commonly solved using dynamic programming. Problem Statement: Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Example: Approach: Code Implementations in Multiple Languages: 1. C Code: #include <stdio.h>#include <string.h>#include <stdbool.h>// Helper function to check if a string can be segmented into words from the dictionarybool wordBreak(char *s, char **wordDict, int wordDictSize) { int n = strlen(s); // DP array to store if s[0..i] can be segmented bool dp[n + 1]; memset(dp, 0, sizeof(dp)); dp[0] = true; // Empty string can always be segmented // Convert wordDict into a hash set for O(1) lookups bool wordDictSet[1000] = {0}; // Assuming wordDict size is less than 1000 for (int i = 0; i < wordDictSize; i++) { wordDictSet[hashString(wordDict[i])] = true; } // Loop through each substring of s for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordDictSet[hashString(s + j)]) { dp[i] = true; break; } } } return dp[n];}int hashString(char *str) { int hash = 0; while (*str) { hash = (hash * 31 + *str++) % 1000; } return hash;}int main() { char *wordDict[] = {“leet”, “code”}; int wordDictSize = 2; char s[] = “leetcode”; if (wordBreak(s, wordDict, wordDictSize)) { printf(“true\n”); } else { printf(“false\n”); } return 0;} 2. Python Code: def wordBreak(s, wordDict): n = len(s) # Create a DP array to store whether s[0..i] can be segmented dp = [False] * (n + 1) dp[0] = True # Empty string can always be segmented # Create a set of words for faster lookup word_set = set(wordDict) for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n]# Test cases = “leetcode”wordDict = [“leet”, “code”]print(wordBreak(s, wordDict)) # Output: True 3. C++ Code: #include <iostream>#include <vector>#include <unordered_set>#include <string>using namespace std;bool wordBreak(string s, unordered_set<string>& wordDict) { int n = s.length(); vector<bool> dp(n + 1, false); dp[0] = true; // Empty string can always be segmented for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordDict.find(s.substr(j, i – j)) != wordDict.end()) { dp[i] = true; break; } } } return dp[n];}int main() { unordered_set<string> wordDict = {“leet”, “code”}; string s = “leetcode”; if (wordBreak(s, wordDict)) { cout << “true” << endl; } else { cout << “false” << endl; } return 0;} 4. Java Code: import java.util.*;public class Solution { public boolean wordBreak(String s, List<String> wordDict) { int n = s.length(); // DP array to store whether s[0..i] can be segmented boolean[] dp = new boolean[n + 1]; dp[0] = true; // Empty string can always be segmented // Convert wordDict to a set for O(1) lookups Set<String> wordSet = new HashSet<>(wordDict); for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; } public static void main(String[] args) { Solution solution = new Solution(); List<String> wordDict = Arrays.asList(“leet”, “code”); String s = “leetcode”; System.out.println(solution.wordBreak(s, wordDict)); // Output: true }} 5. C# Code: using System;using System.Collections.Generic;public class Solution { public bool WordBreak(string s, IList<string> wordDict) { int n = s.Length; // DP array to store whether s[0..i] can be segmented bool[] dp = new bool[n + 1]; dp[0] = true; // Empty string can always be segmented // Convert wordDict to a hash set for O(1) lookups HashSet<string> wordSet = new HashSet<string>(wordDict); for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.Contains(s.Substring(j, i – j))) { dp[i] = true; break; } } } return dp[n]; } public static void Main(string[] args) { Solution solution = new Solution(); List<string> wordDict = new List<string> { “leet”, “code” }; string s = “leetcode”; Console.WriteLine(solution.WordBreak(s, wordDict)); // Output: true }} 6. JavaScript Code: function wordBreak(s, wordDict) { let n = s.length; let dp = Array(n + 1).fill(false); dp[0] = true; // Empty string can always be segmented // Create a set of words for faster lookup let wordSet = new Set(wordDict); for (let i = 1; i <= n; i++) { for (let j = 0; j < i; j++) { if (dp[j] && wordSet.has(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n];}// Test caselet s = “leetcode”;let wordDict = [“leet”, “code”];console.log(wordBreak(s, wordDict)); // Output: true Time and Space Complexity: Conclusion: The Word Break problem is a classic dynamic programming problem where we maintain a dp[] array to track whether substrings of the given string can be segmented into valid words from the dictionary. The solution involves iterating over all substrings and checking if they exist in the dictionary, ensuring an efficient solution for string segmentation problems.

Problem: Palindrome Partitioning II Problem Statement: Given a string s, you need to partition s into the minimum number of substrings such that each substring is a palindrome. Return the minimum number of cuts required to achieve this partition. A palindrome is a string that reads the same backward as forward. Example 1: Input: pythonCopy codes = “aab” Output: pythonCopy code1 Explanation: The optimal partition is “aa”, “b”. Only one cut is needed. Example 2: Input: pythonCopy codes = “a” Output: pythonCopy code0 Explanation: The string “a” is already a palindrome, so no cuts are needed. Example 3: Input: pythonCopy codes = “ab” Output: pythonCopy code1 Explanation: The optimal partition is “a”, “b”. One cut is required. Approach: To solve this problem efficiently, we can use Dynamic Programming (DP). The key idea is to break down the problem into subproblems where: Dynamic Programming Approach: Time Complexity: Algorithm Implementation Python Code pythonCopy codedef minCut(s): n = len(s) # Step 1: Precompute palindrome table isPalindrome = [[False] * n for _ in range(n)] for i in range(n): isPalindrome[i][i] = True # A single character is always a palindrome for i in range(n – 1): if s[i] == s[i + 1]: isPalindrome[i][i + 1] = True # Two consecutive characters are a palindrome if they are the same # Fill the palindrome table for length in range(3, n + 1): # Check for palindromes of length 3 to n for i in range(n – length + 1): j = i + length – 1 if s[i] == s[j] and isPalindrome[i + 1][j – 1]: isPalindrome[i][j] = True # Step 2: DP array to find the minimum cuts dp = [0] * n for i in range(n): if isPalindrome[0][i]: dp[i] = 0 # No cuts needed if the entire substring is a palindrome else: dp[i] = float(‘inf’) for j in range(i): if isPalindrome[j + 1][i]: dp[i] = min(dp[i], dp[j] + 1) return dp[n – 1] # Example test cases print(minCut(“aab”)) # Output: 1 print(minCut(“a”)) # Output: 0 print(minCut(“ab”)) # Output: 1 C++ Code cppCopy code#include <iostream> #include <vector> #include <string> #include <climits> using namespace std; class Solution { public: int minCut(string s) { int n = s.length(); // Step 1: Precompute palindrome table vector<vector<bool>> isPalindrome(n, vector<bool>(n, false)); for (int i = 0; i < n; ++i) { isPalindrome[i][i] = true; // A single character is always a palindrome } for (int i = 0; i < n – 1; ++i) { if (s[i] == s[i + 1]) { isPalindrome[i][i + 1] = true; // Two consecutive characters are palindrome if they are the same } } // Fill the palindrome table for (int length = 3; length <= n; ++length) { for (int i = 0; i <= n – length; ++i) { int j = i + length – 1; if (s[i] == s[j] && isPalindrome[i + 1][j – 1]) { isPalindrome[i][j] = true; } } } // Step 2: DP array to find the minimum cuts vector<int> dp(n, 0); for (int i = 0; i < n; ++i) { if (isPalindrome[0][i]) { dp[i] = 0; // No cuts needed if the entire substring is a palindrome } else { dp[i] = INT_MAX; for (int j = 0; j < i; ++j) { if (isPalindrome[j + 1][i]) { dp[i] = min(dp[i], dp[j] + 1); } } } } return dp[n – 1]; } }; int main() { Solution solution; cout << solution.minCut(“aab”) << endl; // Output: 1 cout << solution.minCut(“a”) << endl; // Output: 0 cout << solution.minCut(“ab”) << endl; // Output: 1 return 0; } Java Code javaCopy codeimport java.util.*; public class Solution { public int minCut(String s) { int n = s.length(); // Step 1: Precompute palindrome table boolean[][] isPalindrome = new boolean[n][n]; for (int i = 0; i < n; ++i) { isPalindrome[i][i] = true; // A single character is always a palindrome } for (int i = 0; i < n – 1; ++i) { if (s.charAt(i) == s.charAt(i + 1)) { isPalindrome[i][i + 1] = true; // Two consecutive characters are palindrome if they are the same } } // Fill the palindrome table for (int length = 3; length <= n; ++length) { for (int i = 0; i <= n – length; ++i) { int j = i + length – 1; if (s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j – 1]) { isPalindrome[i][j] = true; } } } // Step 2: DP array to find the minimum cuts int[] dp = new int[n]; for (int i = 0; i < n; ++i) { if (isPalindrome[0][i]) { dp[i] = 0; // No cuts needed if the entire substring is a palindrome } else { dp[i] = Integer.MAX_VALUE; for (int j = 0; j < i; ++j) { if (isPalindrome[j + 1][i]) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } } return dp[n – 1]; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.minCut(“aab”)); // Output: 1 System.out.println(solution.minCut(“a”)); // Output: 0 System.out.println(solution.minCut(“ab”)); // Output: 1 } } C# Code csharpCopy codeusing System; using System.Collections.Generic; public class Solution { public int MinCut(string s) { int n = s.Length; // Step 1: Precompute palindrome table bool[,] isPalindrome = new bool[n, n]; for (int i = 0; i < n; ++i) { isPalindrome[i, i] = true; // A single character is always a palindrome } for (int i = 0; i < n – 1; ++i) { if (s[i] == s[i + 1]) { isPalindrome[i, i + 1] = true; // Two consecutive characters are palindrome if they are the same } } // Fill the palindrome table for (int length = 3; length <= n; ++length) { for (int i = 0; i <= n – length; ++i) { int j = i + length – 1; if (s[i] == s[j] && isPalindrome[i + 1, j – 1]) { isPalindrome[i, j] = true; } } } // Step 2: DP array to find the minimum cuts int[] dp = new int[n]; for

Problem: Palindrome Partitioning Problem Statement: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. A palindrome is a string that reads the same backward as forward. Example 1: Input: s = “aab” Output: [ [“a”, “a”, “b”], [“aa”, “b”]] Explanation: The palindrome partitions of “aab” are: Example 2: Input: pythonCopy codes = “a” Output: [ [“a”]] Approach: The task is to find all possible ways to partition a string such that every substring is a palindrome. We can use backtracking to explore all possible partitions of the string. For each partition, we check if the substring is a palindrome. If it is, we continue exploring further; if it’s not, we prune the search. Steps: Time Complexity: Algorithm Implementation Python Code def partition(s): def is_palindrome(sub): return sub == sub[::-1] def backtrack(start, path): if start == len(s): result.append(path[:]) # Make a copy of path and add it to result return for end in range(start + 1, len(s) + 1): substring = s[start:end] if is_palindrome(substring): path.append(substring) backtrack(end, path) path.pop() # Backtrack result = [] backtrack(0, []) return result# Example test casesprint(partition(“aab”))print(partition(“a”)) C++ Code #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: vector<vector<string>> partition(string s) { vector<vector<string>> result; vector<string> current; backtrack(s, 0, current, result); return result; }private: bool isPalindrome(const string& str) { int left = 0, right = str.size() – 1; while (left < right) { if (str[left] != str[right]) return false; left++; right–; } return true; } void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) { if (start == s.size()) { result.push_back(current); return; } for (int end = start + 1; end <= s.size(); ++end) { string substring = s.substr(start, end – start); if (isPalindrome(substring)) { current.push_back(substring); backtrack(s, end, current, result); current.pop_back(); // Backtrack } } }};int main() { Solution solution; vector<vector<string>> result = solution.partition(“aab”); for (const auto& partition : result) { for (const auto& str : partition) { cout << str << ” “; } cout << endl; } return 0;} Java Code import java.util.*;public class PalindromePartitioning { public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), result); return result; } private void backtrack(String s, int start, List<String> current, List<List<String>> result) { if (start == s.length()) { result.add(new ArrayList<>(current)); return; } for (int end = start + 1; end <= s.length(); end++) { String substring = s.substring(start, end); if (isPalindrome(substring)) { current.add(substring); backtrack(s, end, current, result); current.remove(current.size() – 1); // Backtrack } } } private boolean isPalindrome(String str) { int left = 0, right = str.length() – 1; while (left < right) { if (str.charAt(left) != str.charAt(right)) { return false; } left++; right–; } return true; } public static void main(String[] args) { PalindromePartitioning solution = new PalindromePartitioning(); List<List<String>> result = solution.partition(“aab”); for (List<String> partition : result) { System.out.println(partition); } }} C# Code using System;using System.Collections.Generic;public class Solution { public IList<IList<string>> Partition(string s) { IList<IList<string>> result = new List<IList<string>>(); Backtrack(s, 0, new List<string>(), result); return result; } private void Backtrack(string s, int start, List<string> current, IList<IList<string>> result) { if (start == s.Length) { result.Add(new List<string>(current)); return; } for (int end = start + 1; end <= s.Length; end++) { string substring = s.Substring(start, end – start); if (IsPalindrome(substring)) { current.Add(substring); Backtrack(s, end, current, result); current.RemoveAt(current.Count – 1); // Backtrack } } } private bool IsPalindrome(string str) { int left = 0, right = str.Length – 1; while (left < right) { if (str[left] != str[right]) return false; left++; right–; } return true; } public static void Main() { Solution solution = new Solution(); var result = solution.Partition(“aab”); foreach (var partition in result) { Console.WriteLine(string.Join(” “, partition)); } }} JavaScript Code function partition(s) { const result = []; function backtrack(start, current) { if (start === s.length) { result.push([…current]); return; } for (let end = start + 1; end <= s.length; end++) { let substring = s.slice(start, end); if (isPalindrome(substring)) { current.push(substring); backtrack(end, current); current.pop(); // Backtrack } } } function isPalindrome(str) { let left = 0, right = str.length – 1; while (left < right) { if (str[left] !== str[right]) return false; left++; right–; } return true; } backtrack(0, []); return result;}// Example usageconsole.log(partition(“aab”)); Summary of the Approach: Time Complexity:

Problem: Word Ladder Problem Statement: Given two words, beginWord and endWord, and a dictionary wordList, find the length of the shortest transformation sequence from beginWord to endWord, such that: Note: Example 1: Input: beginWord = “hit”endWord = “cog”wordList = [“hot”, “dot”, “dog”, “lot”, “log”, “cog”] Output: 5 Explanation: The shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, which is 5 words long. Example 2: Input: beginWord = “hit”endWord = “cog”wordList = [“hot”, “dot”, “dog”, “lot”, “log”] Output: 0 Explanation: There is no possible transformation sequence from hit to cog because the word cog is not in the word list. Approach: The problem can be thought of as finding the shortest path in an unweighted graph, where: Steps: Time Complexity: Algorithm: Code Implementations 1. Python Code from collections import dequedef ladderLength(beginWord, endWord, wordList): if endWord not in wordList: return 0 wordList.add(beginWord) queue = deque([(beginWord, 1)]) # (current_word, current_length) visited = set([beginWord]) while queue: word, length = queue.popleft() # Try changing each character of the word for i in range(len(word)): for c in ‘abcdefghijklmnopqrstuvwxyz’: new_word = word[:i] + c + word[i+1:] if new_word == endWord: return length + 1 if new_word in wordList and new_word not in visited: visited.add(new_word) queue.append((new_word, length + 1)) return 0# Example test casesbeginWord = “hit”endWord = “cog”wordList = set([“hot”, “dot”, “dog”, “lot”, “log”, “cog”])print(ladderLength(beginWord, endWord, wordList)) # Output: 5 2. C++ Code #include <iostream>#include <unordered_set>#include <queue>#include <string>using namespace std;int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) { if (wordList.find(endWord) == wordList.end()) return 0; wordList.insert(beginWord); queue<pair<string, int>> q; // {current_word, length} unordered_set<string> visited; q.push({beginWord, 1}); visited.insert(beginWord); while (!q.empty()) { auto [word, length] = q.front(); q.pop(); // Try changing each character of the word for (int i = 0; i < word.length(); i++) { char original = word[i]; for (char c = ‘a’; c <= ‘z’; c++) { word[i] = c; if (word == endWord) return length + 1; if (wordList.find(word) != wordList.end() && visited.find(word) == visited.end()) { visited.insert(word); q.push({word, length + 1}); } } word[i] = original; // Restore original character } } return 0;}int main() { string beginWord = “hit”; string endWord = “cog”; unordered_set<string> wordList = {“hot”, “dot”, “dog”, “lot”, “log”, “cog”}; cout << ladderLength(beginWord, endWord, wordList) << endl; // Output: 5 return 0;} 3. Java Code import java.util.*;public class WordLadder { public int ladderLength(String beginWord, String endWord, Set<String> wordList) { if (!wordList.contains(endWord)) return 0; wordList.add(beginWord); Queue<Pair<String, Integer>> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.offer(new Pair<>(beginWord, 1)); visited.add(beginWord); while (!queue.isEmpty()) { Pair<String, Integer> current = queue.poll(); String word = current.getKey(); int length = current.getValue(); for (int i = 0; i < word.length(); i++) { char[] temp = word.toCharArray(); for (char c = ‘a’; c <= ‘z’; c++) { temp[i] = c; String newWord = new String(temp); if (newWord.equals(endWord)) return length + 1; if (wordList.contains(newWord) && !visited.contains(newWord)) { visited.add(newWord); queue.offer(new Pair<>(newWord, length + 1)); } } } } return 0; } public static void main(String[] args) { WordLadder wl = new WordLadder(); Set<String> wordList = new HashSet<>(Arrays.asList(“hot”, “dot”, “dog”, “lot”, “log”, “cog”)); System.out.println(wl.ladderLength(“hit”, “cog”, wordList)); // Output: 5 }}class Pair<K, V> { K key; V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; }} 4. C# Code using System;using System.Collections.Generic;public class WordLadder { public int LadderLength(string beginWord, string endWord, HashSet<string> wordList) { if (!wordList.Contains(endWord)) return 0; wordList.Add(beginWord); Queue<KeyValuePair<string, int>> queue = new Queue<KeyValuePair<string, int>>(); HashSet<string> visited = new HashSet<string>(); queue.Enqueue(new KeyValuePair<string, int>(beginWord, 1)); visited.Add(beginWord); while (queue.Count > 0) { var current = queue.Dequeue(); string word = current.Key; int length = current.Value; for (int i = 0; i < word.Length; i++) { char[] temp = word.ToCharArray(); for (char c = ‘a’; c <= ‘z’; c++) { temp[i] = c; string newWord = new string(temp); if (newWord == endWord) return length + 1; if (wordList.Contains(newWord) && !visited.Contains(newWord)) { visited.Add(newWord); queue.Enqueue(new KeyValuePair<string, int>(newWord, length + 1)); } } } } return 0; } public static void Main() { WordLadder wl = new WordLadder(); HashSet<string> wordList = new HashSet<string> { “hot”, “dot”, “dog”, “lot”, “log”, “cog” }; Console.WriteLine(wl.LadderLength(“hit”, “cog”, wordList)); // Output: 5 }} 5. JavaScript Code function ladderLength(beginWord, endWord, wordList) { if (!wordList.has(endWord)) return 0; wordList.add(beginWord); let queue = [[beginWord, 1]]; // [current_word, current_length] let visited = new Set([beginWord]); while (queue.length > 0) { let [word, length] = queue.shift(); for (let i = 0; i < word.length; i++) { for (let c = ‘a’; c <= ‘z’; c++) { let newWord = word.slice(0, i) + c + word.slice(i + 1); if (newWord === endWord) return length + 1; if (wordList.has(newWord) && !visited.has(newWord)) { visited.add(newWord); queue.push([newWord, length + 1]); } } } } return 0;}// Example test caseslet beginWord = “hit”;let endWord = “cog”;let wordList = new Set([“hot”, “dot”, “dog”, “lot”, “log”, “cog”]);console.log(ladderLength(beginWord, endWord, wordList)); // Output: 5 Summary of Code Logic: Time Complexity:

Problem: Valid Palindrome Problem Statement: Given a string s, determine if it is a valid palindrome, considering only alphanumeric characters and ignoring case. A palindrome is a string that reads the same forward and backward. Note: Example 1: Input: s = “A man, a plan, a canal, Panama” Output: true Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes: “amanaplanacanalpanama”, which is a palindrome. Example 2: Input: s = “race a car” Output: false Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes: “raceacar”, which is not a palindrome. Constraints: Approach: We can use a two-pointer technique to check whether a string is a valid palindrome: Time Complexity: Code Implementations in Multiple Languages: 1. C #include <stdio.h>#include <ctype.h>#include <string.h>int isPalindrome(char *s) { int left = 0, right = strlen(s) – 1; while (left < right) { // Move left pointer to the next alphanumeric character while (left < right && !isalnum(s[left])) { left++; } // Move right pointer to the previous alphanumeric character while (left < right && !isalnum(s[right])) { right–; } // Compare characters case-insensitively if (tolower(s[left]) != tolower(s[right])) { return 0; // Not a palindrome } left++; right–; } return 1; // Is a palindrome}int main() { char s[] = “A man, a plan, a canal, Panama”; if (isPalindrome(s)) { printf(“true\n”); } else { printf(“false\n”); } return 0;} 2. C++ #include <iostream>#include <cctype>#include <string>using namespace std;bool isPalindrome(string s) { int left = 0, right = s.length() – 1; while (left < right) { // Move left pointer to the next alphanumeric character while (left < right && !isalnum(s[left])) { left++; } // Move right pointer to the previous alphanumeric character while (left < right && !isalnum(s[right])) { right–; } // Compare characters case-insensitively if (tolower(s[left]) != tolower(s[right])) { return false; // Not a palindrome } left++; right–; } return true; // Is a palindrome}int main() { string s = “A man, a plan, a canal, Panama”; cout << (isPalindrome(s) ? “true” : “false”) << endl; return 0;} 3. Java public class Main { public static boolean isPalindrome(String s) { int left = 0, right = s.length() – 1; while (left < right) { // Move left pointer to the next alphanumeric character while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { left++; } // Move right pointer to the previous alphanumeric character while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { right–; } // Compare characters case-insensitively if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { return false; // Not a palindrome } left++; right–; } return true; // Is a palindrome } public static void main(String[] args) { String s = “A man, a plan, a canal, Panama”; System.out.println(isPalindrome(s)); }} 4. Python def isPalindrome(s: str) -> bool: left, right = 0, len(s) – 1 while left < right: # Move left pointer to the next alphanumeric character while left < right and not s[left].isalnum(): left += 1 # Move right pointer to the previous alphanumeric character while left < right and not s[right].isalnum(): right -= 1 # Compare characters case-insensitively if s[left].lower() != s[right].lower(): return False left += 1 right -= 1 return True# Test cases = “A man, a plan, a canal, Panama”print(isPalindrome(s)) # Output: True 5. C# using System;class Program { public static bool IsPalindrome(string s) { int left = 0, right = s.Length – 1; while (left < right) { // Move left pointer to the next alphanumeric character while (left < right && !Char.IsLetterOrDigit(s[left])) { left++; } // Move right pointer to the previous alphanumeric character while (left < right && !Char.IsLetterOrDigit(s[right])) { right–; } // Compare characters case-insensitively if (Char.ToLower(s[left]) != Char.ToLower(s[right])) { return false; } left++; right–; } return true; } static void Main() { string s = “A man, a plan, a canal, Panama”; Console.WriteLine(IsPalindrome(s)); // Output: True }} 6. JavaScript function isPalindrome(s) { let left = 0, right = s.length – 1; while (left < right) { // Move left pointer to the next alphanumeric character while (left < right && !/[a-zA-Z0-9]/.test(s[left])) { left++; } // Move right pointer to the previous alphanumeric character while (left < right && !/[a-zA-Z0-9]/.test(s[right])) { right–; } // Compare characters case-insensitively if (s[left].toLowerCase() !== s[right].toLowerCase()) { return false; } left++; right–; } return true;}// Test caseconst s = “A man, a plan, a canal, Panama”;console.log(isPalindrome(s)); // Output: true Summary:

The problem “Distinct Subsequences“ asks for the number of distinct subsequences of a string s that match a string t. This is a well-known dynamic programming problem and can be efficiently solved using a 2D dynamic programming table. Problem Statement: Given a string s and a string t, find the number of distinct subsequences of s which equals t. A subsequence is derived from another string by deleting some or no characters without changing the order of the remaining characters. Example 1: Input: s = “rabbbit”, t = “rabbit” Output: 3 Explanation: There are three distinct subsequences of “rabbbit” which equal “rabbit”: Example 2: Input: s = “axaxb”, t = “ab” Output: 4 Explanation: There are four distinct subsequences of “axaxb” which equal “ab”: Approach: We use a dynamic programming approach to solve this problem. Let dp[i][j] represent the number of ways to form the first j characters of t using the first i characters of s. The recurrence relation is as follows: The final answer is dp[len(s)][len(t)]. Time Complexity: Now, let’s implement this solution in different languages. C Code: #include <stdio.h>#include <string.h>int numDistinct(char *s, char *t) { int m = strlen(s), n = strlen(t); int dp[m+1][n+1]; // Initialize the dp array for (int i = 0; i <= m; i++) { dp[i][0] = 1; // There’s 1 way to form empty t } for (int j = 1; j <= n; j++) { dp[0][j] = 0; // There’s no way to form a non-empty t from empty s } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i-1] == t[j-1]) { dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; } else { dp[i][j] = dp[i-1][j]; } } } return dp[m][n];}int main() { char s[] = “rabbbit”, t[] = “rabbit”; printf(“Number of distinct subsequences: %d\n”, numDistinct(s, t)); return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;int numDistinct(string s, string t) { int m = s.length(), n = t.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // Base case: dp[i][0] = 1 for (int i = 0; i <= m; i++) { dp[i][0] = 1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i – 1] == t[j – 1]) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n];}int main() { string s = “rabbbit”, t = “rabbit”; cout << “Number of distinct subsequences: ” << numDistinct(s, t) << endl; return 0;} Java Code: public class Main { public static int numDistinct(String s, String t) { int m = s.length(), n = t.length(); int[][] dp = new int[m + 1][n + 1]; // Base case: dp[i][0] = 1 for (int i = 0; i <= m; i++) { dp[i][0] = 1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s.charAt(i – 1) == t.charAt(j – 1)) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n]; } public static void main(String[] args) { String s = “rabbbit”, t = “rabbit”; System.out.println(“Number of distinct subsequences: ” + numDistinct(s, t)); }} Python Code: def numDistinct(s, t): m, n = len(s), len(t) dp = [[0] * (n + 1) for _ in range(m + 1)] # Base case: dp[i][0] = 1 for i in range(m + 1): dp[i][0] = 1 for i in range(1, m + 1): for j in range(1, n + 1): if s[i – 1] == t[j – 1]: dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j] else: dp[i][j] = dp[i – 1][j] return dp[m][n]# Test cases = “rabbbit”t = “rabbit”print(“Number of distinct subsequences:”, numDistinct(s, t)) C# Code: using System;class Program { public static int NumDistinct(string s, string t) { int m = s.Length, n = t.Length; int[,] dp = new int[m + 1, n + 1]; // Base case: dp[i][0] = 1 for (int i = 0; i <= m; i++) { dp[i, 0] = 1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i – 1] == t[j – 1]) { dp[i, j] = dp[i – 1, j – 1] + dp[i – 1, j]; } else { dp[i, j] = dp[i – 1, j]; } } } return dp[m, n]; } static void Main() { string s = “rabbbit”, t = “rabbit”; Console.WriteLine(“Number of distinct subsequences: ” + NumDistinct(s, t)); }} JavaScript Code: function numDistinct(s, t) { const m = s.length, n = t.length; let dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0)); // Base case: dp[i][0] = 1 for (let i = 0; i <= m; i++) { dp[i][0] = 1; } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (s[i – 1] === t[j – 1]) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n];}// Test caseconst s = “rabbbit”, t = “rabbit”;console.log(“Number of distinct subsequences:”, numDistinct(s, t)); Summary: This problem can be efficiently solved using dynamic programming, and the code above provides solutions for C, C++, Java, Python, C#, and JavaScript. The time complexity for all the solutions is O(m×n)O(m \times n)O(m×n), where mmm and nnn are the lengths of strings s and t, respectively.

Determine the biggest rectangular area a given histogram can have where a number of adjacent bars allow the biggest rectangle to be formed. Assume for simplicity that the width of all bars is one unit. Take the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6} for instance. Twelve is the largest rectangle that may be formed; the max area rectangle is underlined in red below. One may find a straightforward solution by first considering all bars as points of reference and then computing the area of every rectangle beginning with each bar. At last return maximum of all conceivable areas. O(n^2) would be the time complexity of this solution. Solving this in O(nLogn) time will require Divide and Conquer. Finding the least value in the given array is the aim. The maximum area follows three values once we have index of the minimum value. C++ Java Python C# Output Maximum area is 12 Time Complexity: O(N log N) Auxiliary Space: O(N)