SkylineWebZ

Problem Statement: Maximum Product Subarray Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest product and return its product. Example Example 1: Input:nums = [2, 3, -2, 4]Output:6Explanation: The subarray [2, 3] has the largest product 6. Example 2: Input:nums = [-2, 0, -1]Output:0Explanation: The subarray [0] has the largest product 0. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <limits.h>int maxProduct(int* nums, int numsSize) { if (numsSize == 0) return 0; int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < numsSize; i++) { if (nums[i] < 0) { // Swap maxProd and minProd when nums[i] is negative int temp = maxProd; maxProd = minProd; minProd = temp; } maxProd = (nums[i] > nums[i] * maxProd) ? nums[i] : nums[i] * maxProd; minProd = (nums[i] < nums[i] * minProd) ? nums[i] : nums[i] * minProd; result = (result > maxProd) ? result : maxProd; } return result;}int main() { int nums[] = {2, 3, -2, 4}; int size = sizeof(nums) / sizeof(nums[0]); printf(“Maximum product subarray: %d\n”, maxProduct(nums, size)); // Output: 6 return 0;} C++ #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxProduct(vector<int>& nums) { if (nums.empty()) return 0; int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < nums.size(); i++) { if (nums[i] < 0) { swap(maxProd, minProd); } maxProd = max(nums[i], nums[i] * maxProd); minProd = min(nums[i], nums[i] * minProd); result = max(result, maxProd); } return result;}int main() { vector<int> nums = {2, 3, -2, 4}; cout << “Maximum product subarray: ” << maxProduct(nums) << endl; // Output: 6 return 0;} Java public class MaximumProductSubarray { public static int maxProduct(int[] nums) { if (nums.length == 0) return 0; int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] < 0) { int temp = maxProd; maxProd = minProd; minProd = temp; } maxProd = Math.max(nums[i], nums[i] * maxProd); minProd = Math.min(nums[i], nums[i] * minProd); result = Math.max(result, maxProd); } return result; } public static void main(String[] args) { int[] nums = {2, 3, -2, 4}; System.out.println(“Maximum product subarray: ” + maxProduct(nums)); // Output: 6 }} Python def maxProduct(nums): if not nums: return 0 maxProd = minProd = result = nums[0] for num in nums[1:]: if num < 0: maxProd, minProd = minProd, maxProd maxProd = max(num, num * maxProd) minProd = min(num, num * minProd) result = max(result, maxProd) return result# Examplenums = [2, 3, -2, 4]print(“Maximum product subarray:”, maxProduct(nums)) # Output: 6 C# using System;public class MaximumProductSubarray { public static int MaxProduct(int[] nums) { if (nums.Length == 0) return 0; int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < nums.Length; i++) { if (nums[i] < 0) { int temp = maxProd; maxProd = minProd; minProd = temp; } maxProd = Math.Max(nums[i], nums[i] * maxProd); minProd = Math.Min(nums[i], nums[i] * minProd); result = Math.Max(result, maxProd); } return result; } public static void Main() { int[] nums = {2, 3, -2, 4}; Console.WriteLine(“Maximum product subarray: ” + MaxProduct(nums)); // Output: 6 }} JavaScript function maxProduct(nums) { if (nums.length === 0) return 0; let maxProd = nums[0], minProd = nums[0], result = nums[0]; for (let i = 1; i < nums.length; i++) { if (nums[i] < 0) { [maxProd, minProd] = [minProd, maxProd]; } maxProd = Math.max(nums[i], nums[i] * maxProd); minProd = Math.min(nums[i], nums[i] * minProd); result = Math.max(result, maxProd); } return result;}console.log(“Maximum product subarray:”, maxProduct([2, 3, -2, 4])); // Output: 6 Summary

Problem Statement: Word Break II Given a string s and a list of words wordDict, return all possible sentence(s) where each sentence is a valid segmentation of s into words from wordDict. The solution should return a list of all possible sentences. Note: Example Example 1: Input:”catsanddog”wordDict = [“cat”, “cats”, “and”, “sand”, “dog”] Output:[“cats and dog”, “cat sand dog”] Example 2: Input:”pineapplepenapple”wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”] Output:[“pine apple pen apple”, “pineapple pen apple”, “pine applepen apple”] Example 3: Input:”catsandog”wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] Output:[] Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>#define MAX 1000void findWordBreaks(char* s, int start, char** wordDict, int wordDictSize, bool* dp, char*** result, int* returnSize) { if (start == strlen(s)) { result[*returnSize] = malloc(sizeof(char*) * 2); result[*returnSize][0] = strdup(“”); (*returnSize)++; return; } if (!dp[start]) return; // Skip if this position cannot be reached for (int i = 0; i < wordDictSize; i++) { int len = strlen(wordDict[i]); if (start + len <= strlen(s) && strncmp(s + start, wordDict[i], len) == 0) { char** tempResult; int tempSize = 0; findWordBreaks(s, start + len, wordDict, wordDictSize, dp, &tempResult, &tempSize); for (int j = 0; j < tempSize; j++) { int newSize = tempSize + 1; result[*returnSize] = realloc(result[*returnSize], sizeof(char*) * newSize); char* newSentence = malloc(strlen(wordDict[i]) + strlen(tempResult[j]) + 2); sprintf(newSentence, “%s %s”, wordDict[i], tempResult[j]); result[*returnSize][newSize – 1] = newSentence; } } }}int main() { char* s = “catsanddog”; char* wordDict[] = {“cat”, “cats”, “and”, “sand”, “dog”}; int wordDictSize = 5; bool dp[MAX]; memset(dp, 0, sizeof(dp)); char*** result = malloc(sizeof(char**) * MAX); int returnSize = 0; findWordBreaks(s, 0, wordDict, wordDictSize, dp, result, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i][0]); } return 0;} C++ #include <iostream>#include <vector>#include <unordered_set>#include <string>#include <algorithm>using namespace std;void dfs(string s, unordered_set<string>& wordSet, vector<string>& currentSentence, vector<string>& result, vector<bool>& dp) { if (s.empty()) { string sentence = “”; for (int i = 0; i < currentSentence.size(); i++) { sentence += currentSentence[i]; if (i != currentSentence.size() – 1) sentence += ” “; } result.push_back(sentence); return; } if (!dp[s.size()]) return; for (int i = 1; i <= s.size(); i++) { string word = s.substr(0, i); if (wordSet.find(word) != wordSet.end()) { currentSentence.push_back(word); dfs(s.substr(i), wordSet, currentSentence, result, dp); currentSentence.pop_back(); } }}vector<string> wordBreak(string s, unordered_set<string>& wordSet) { int n = s.length(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.find(s.substr(j, i – j)) != wordSet.end()) { dp[i] = true; break; } } } vector<string> result; vector<string> currentSentence; if (dp[n]) dfs(s, wordSet, currentSentence, result, dp); sort(result.begin(), result.end()); return result;}int main() { unordered_set<string> wordSet = {“cat”, “cats”, “and”, “sand”, “dog”}; string s = “catsanddog”; vector<string> result = wordBreak(s, wordSet); for (const auto& sentence : result) { cout << sentence << endl; } return 0;} Java import java.util.*;public class WordBreakII { public static void dfs(String s, Set<String> wordSet, List<String> currentSentence, List<String> result, boolean[] dp) { if (s.isEmpty()) { result.add(String.join(” “, currentSentence)); return; } if (!dp[s.length()]) return; for (int i = 1; i <= s.length(); i++) { String word = s.substring(0, i); if (wordSet.contains(word)) { currentSentence.add(word); dfs(s.substring(i), wordSet, currentSentence, result, dp); currentSentence.remove(currentSentence.size() – 1); } } } public static List<String> wordBreak(String s, Set<String> wordSet) { int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; 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; } } } List<String> result = new ArrayList<>(); if (dp[n]) { List<String> currentSentence = new ArrayList<>(); dfs(s, wordSet, currentSentence, result, dp); } Collections.sort(result); return result; } public static void main(String[] args) { Set<String> wordSet = new HashSet<>(Arrays.asList(“cat”, “cats”, “and”, “sand”, “dog”)); String s = “catsanddog”; List<String> result = wordBreak(s, wordSet); for (String sentence : result) { System.out.println(sentence); } }} Python pythonCopy codedef dfs(s, wordSet, currentSentence, result, dp): if not s: result.append(” “.join(currentSentence)) return if not dp[len(s)]: return for i in range(1, len(s) + 1): word = s[:i] if word in wordSet: currentSentence.append(word) dfs(s[i:], wordSet, currentSentence, result, dp) currentSentence.pop() def wordBreak(s, wordDict): wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in wordSet: dp[i] = True break result = [] if dp[n]: currentSentence = [] dfs(s, wordSet, currentSentence, result, dp) result.sort() return result # Example s = “catsanddog” wordDict = [“cat”, “cats”, “and”, “sand”, “dog”] print(wordBreak(s, wordDict)) # Output: [“cats and dog”, “cat sand dog”] C# using System;using System.Collections.Generic;public class WordBreakII { public static void Dfs(string s, HashSet<string> wordSet, List<string> currentSentence, List<string> result, bool[] dp) { if (s.Length == 0) { result.Add(string.Join(” “, currentSentence)); return; } if (!dp[s.Length]) return; for (int i = 1; i <= s.Length; i++) { string word = s.Substring(0, i); if (wordSet.Contains(word)) { currentSentence.Add(word); Dfs(s.Substring(i), wordSet, currentSentence, result, dp); currentSentence.RemoveAt(currentSentence.Count – 1); } } } public static List<string> WordBreak(string s, HashSet<string> wordSet) { int n = s.Length; bool[] dp = new bool[n + 1]; dp[0] = true; 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; } } } List<string> result = new List<string>(); if (dp[n]) { List<string> currentSentence = new List<string>(); Dfs(s, wordSet, currentSentence, result, dp); } result.Sort(); return result; } public static void Main() { HashSet<string> wordSet = new HashSet<string> { “cat”, “cats”, “and”, “sand”, “dog” }; string s = “catsanddog”; List<string> result = WordBreak(s, wordSet); foreach (var sentence in result) { Console.WriteLine(sentence); } }} JavaScript function dfs(s, wordSet, currentSentence, result, dp) { if (s === “”) { result.push(currentSentence.join(” “)); return; } if (!dp[s.length]) return; for (let i = 1; i <= s.length; i++) { const word = s.slice(0, i); if (wordSet.has(word)) { currentSentence.push(word); dfs(s.slice(i), wordSet, currentSentence, result, dp); currentSentence.pop(); } }}function wordBreak(s, wordDict) { const wordSet = new Set(wordDict);

Problem Statement: Word Break 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. Note: Example Example 1: Input: s = “leetcode”, wordDict = [“leet”, “code”]Output: trueExplanation: Return true because “leetcode” can be segmented as “leet code”. Example 2: Input: s = “applepenapple”, wordDict = [“apple”, “pen”]Output: trueExplanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Example 3: Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]Output: falseExplanation: Return false because “catsandog” cannot be segmented into words from the dictionary. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdbool.h>bool wordBreak(char* s, char** wordDict, int wordDictSize) { int n = strlen(s); bool dp[n + 1]; memset(dp, 0, sizeof(dp)); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < wordDictSize; j++) { int len = strlen(wordDict[j]); if (i >= len && dp[i – len] && strncmp(s + i – len, wordDict[j], len) == 0) { dp[i] = true; break; } } } return dp[n];}int main() { char* wordDict[] = {“leet”, “code”}; int wordDictSize = sizeof(wordDict) / sizeof(wordDict[0]); char s[] = “leetcode”; printf(“%d\n”, wordBreak(s, wordDict, wordDictSize)); // Output: 1 (true) return 0;} C++ #include <iostream>#include <vector>#include <unordered_set>#include <string>using namespace std;bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.find(s.substr(j, i – j)) != wordSet.end()) { dp[i] = true; break; } } } return dp[n];}int main() { vector<string> wordDict = {“leet”, “code”}; string s = “leetcode”; cout << wordBreak(s, wordDict) << endl; // Output: 1 (true) return 0;} Java import java.util.*;public class WordBreak { public static boolean wordBreak(String s, List<String> wordDict) { Set<String> wordSet = new HashSet<>(wordDict); int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; 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) { List<String> wordDict = Arrays.asList(“leet”, “code”); String s = “leetcode”; System.out.println(wordBreak(s, wordDict)); // Output: true }} Python def wordBreak(s: str, wordDict: list) -> bool: wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in wordSet: dp[i] = True break return dp[n]# Examples = “leetcode”wordDict = [“leet”, “code”]print(wordBreak(s, wordDict)) # Output: True C# using System;using System.Collections.Generic;public class WordBreak { public static bool WordBreak(string s, IList<string> wordDict) { HashSet<string> wordSet = new HashSet<string>(wordDict); int n = s.Length; bool[] dp = new bool[n + 1]; dp[0] = true; 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() { List<string> wordDict = new List<string> { “leet”, “code” }; string s = “leetcode”; Console.WriteLine(WordBreak(s, wordDict)); // Output: True }} JavaScript function wordBreak(s, wordDict) { const wordSet = new Set(wordDict); const n = s.length; const dp = new Array(n + 1).fill(false); dp[0] = true; 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];}console.log(wordBreak(“leetcode”, [“leet”, “code”])); // Output: true Summary

Problem Statement: Palindrome Partitioning II Given a string s, you need to partition it such that every substring of the partition is a palindrome. Return the minimum number of cuts required to partition s such that every substring is a palindrome. Example Example 1: Input: s = “aab” Output: 1Explanation: The palindrome partitioning [“aa”, “b”] could be made with 1 cut. Example 2: Input: s = “a” Output: 0Explanation: The string is already a palindrome, so no cuts are needed. Example 3: Input: s = “abac” Output: 1Explanation: The palindrome partitioning [“aba”, “c”] could be made with 1 cut. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdbool.h>#define MAX 1000int minCut(char* s) { int n = strlen(s); bool palindrome[n][n]; int dp[n+1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; memset(palindrome, 0, sizeof(palindrome)); for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = (dp[i] < dp[j] + 1) ? dp[i] : dp[j] + 1; } } } return dp[n – 1];}int main() { char s[] = “aab”; printf(“%d\n”, minCut(s)); return 0;} C++ #include <iostream>#include <vector>#include <cstring>using namespace std;int minCut(string s) { int n = s.length(); vector<vector<bool>> palindrome(n, vector<bool>(n, false)); vector<int> dp(n + 1, n); dp[0] = -1; // no cut needed for empty string for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1); } } } return dp[n – 1];}int main() { string s = “aab”; cout << minCut(s) << endl; return 0;} Java public class PalindromePartitioning { public static int minCut(String s) { int n = s.length(); boolean[][] palindrome = new boolean[n][n]; int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s.charAt(i) == s.charAt(j)) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n – 1]; } public static void main(String[] args) { String s = “aab”; System.out.println(minCut(s)); }} Python def minCut(s: str) -> int: n = len(s) palindrome = [[False] * n for _ in range(n)] dp = [i for i in range(-1, n)] for i in range(n – 1, -1, -1): for j in range(i, n): palindrome[i][j] = (s[i] == s[j]) and (j – i <= 2 or palindrome[i + 1][j – 1]) for i in range(n): if palindrome[0][i]: dp[i] = 0 else: for j in range(i): if palindrome[j + 1][i]: dp[i] = min(dp[i], dp[j] + 1) return dp[n – 1]# Examples = “aab”print(minCut(s)) # Output: 1 C# using System;public class PalindromePartitioning { public static int MinCut(string s) { int n = s.Length; bool[,] palindrome = new bool[n, n]; int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i, j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1, j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0, i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1, i]) dp[i] = Math.Min(dp[i], dp[j] + 1); } } } return dp[n – 1]; } public static void Main() { string s = “aab”; Console.WriteLine(MinCut(s)); // Output: 1 }} JavaScript function minCut(s) { const n = s.length; const palindrome = Array.from(Array(n), () => Array(n).fill(false)); const dp = Array.from({ length: n + 1 }, (_, i) => i – 1); for (let i = n – 1; i >= 0; i–) { for (let j = i; j < n; j++) { palindrome[i][j] = (s[i] === s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (let i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (let j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n – 1];}console.log(minCut(“aab”)); // Output: 1 Summary

Problem Statement: Palindrome Partitioning Given a string s, partition the string such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Definition: Example: Example 1: Input: plaintextCopy code”aab” Output: plaintextCopy code[[“a”, “a”, “b”], [“aa”, “b”]] Explanation: The string “aab” can be split in two ways where each substring is a palindrome: Example 2: Input: plaintextCopy code”efe” Output: plaintextCopy code[[“e”, “f”, “e”], [“efe”]] Explanation: The string “efe” can be split into: Approach: We can solve this problem using backtracking and dynamic programming. Backtracking Approach: Algorithm: Code Implementation: 1. C++: #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: bool isPalindrome(const string& s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end–; } return true; } void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) { if (start == s.length()) { result.push_back(current); return; } for (int end = start; end < s.length(); ++end) { if (isPalindrome(s, start, end)) { current.push_back(s.substr(start, end – start + 1)); backtrack(s, end + 1, current, result); current.pop_back(); // backtrack } } } vector<vector<string>> partition(string s) { vector<vector<string>> result; vector<string> current; backtrack(s, 0, current, result); return result; }};int main() { Solution sol; string s = “aab”; vector<vector<string>> result = sol.partition(s); for (const auto& partition : result) { for (const auto& str : partition) { cout << str << ” “; } cout << endl; } return 0;} 2. Java: import java.util.ArrayList;import java.util.List;public class Solution { public boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start) != s.charAt(end)) return false; start++; end–; } return true; } public 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; end < s.length(); ++end) { if (isPalindrome(s, start, end)) { current.add(s.substring(start, end + 1)); backtrack(s, end + 1, current, result); current.remove(current.size() – 1); // backtrack } } } public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); List<String> current = new ArrayList<>(); backtrack(s, 0, current, result); return result; } public static void main(String[] args) { Solution sol = new Solution(); String s = “aab”; List<List<String>> result = sol.partition(s); for (List<String> partition : result) { for (String str : partition) { System.out.print(str + ” “); } System.out.println(); } }} 3. Python: class Solution: def isPalindrome(self, s, start, end): while start < end: if s[start] != s[end]: return False start += 1 end -= 1 return True def backtrack(self, s, start, current, result): if start == len(s): result.append(list(current)) return for end in range(start, len(s)): if self.isPalindrome(s, start, end): current.append(s[start:end+1]) self.backtrack(s, end+1, current, result) current.pop() # backtrack def partition(self, s): result = [] self.backtrack(s, 0, [], result) return result# Example usagesol = Solution()s = “aab”result = sol.partition(s)for partition in result: print(partition) 4. C#: using System;using System.Collections.Generic;public class Solution { public bool IsPalindrome(string s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end–; } return true; } public void Backtrack(string s, int start, List<string> current, List<List<string>> result) { if (start == s.Length) { result.Add(new List<string>(current)); return; } for (int end = start; end < s.Length; ++end) { if (IsPalindrome(s, start, end)) { current.Add(s.Substring(start, end – start + 1)); Backtrack(s, end + 1, current, result); current.RemoveAt(current.Count – 1); // backtrack } } } public List<List<string>> Partition(string s) { List<List<string>> result = new List<List<string>>(); List<string> current = new List<string>(); Backtrack(s, 0, current, result); return result; } public static void Main() { Solution sol = new Solution(); string s = “aab”; List<List<string>> result = sol.Partition(s); foreach (var partition in result) { Console.WriteLine(string.Join(” “, partition)); } }} 5. JavaScript: class Solution { isPalindrome(s, start, end) { while (start < end) { if (s[start] !== s[end]) return false; start++; end–; } return true; } backtrack(s, start, current, result) { if (start === s.length) { result.push([…current]); return; } for (let end = start; end < s.length; ++end) { if (this.isPalindrome(s, start, end)) { current.push(s.substring(start, end + 1)); this.backtrack(s, end + 1, current, result); current.pop(); // backtrack } } } partition(s) { let result = []; this.backtrack(s, 0, [], result); return result; }}// Example usage:let sol = new Solution();let s = “aab”;let result = sol.partition(s);result.forEach(partition => { console.log(partition.join(” “));}); Time and Space Complexity: