SkylineWebZ

The “Scramble String” problem is a classical recursive problem that deals with determining if one string is a scrambled version of another. Problem Statement Given two strings, s1 and s2, check if s2 is a scrambled version of s1. A scrambled string of s1 can be obtained by recursively applying the following operations: Examples Example 1: Input:s1 = “great”, s2 = “rgeat”Output:trueExplanation: Example 2: Input:s1 = “abcde”, s2 = “caebd”Output:false Example 3: Input:s1 = “a”, s2 = “a”Output:true Approach and Algorithm 1. Recursive Approach We recursively check all possible ways to split the strings and validate if either: 2. Dynamic Programming (DP) We use a 3D DP table to store results for substrings of s1 and s2. Complexity Code Implementation C: #include <stdio.h>#include <stdbool.h>#include <string.h>bool isScrambleUtil(char *s1, char *s2, int n) { if (strncmp(s1, s2, n) == 0) return true; if (n == 1) return s1[0] == s2[0]; int freq[26] = {0}; for (int i = 0; i < n; i++) { freq[s1[i] – ‘a’]++; freq[s2[i] – ‘a’]–; } for (int i = 0; i < 26; i++) { if (freq[i] != 0) return false; } for (int i = 1; i < n; i++) { if (isScrambleUtil(s1, s2, i) && isScrambleUtil(s1 + i, s2 + i, n – i)) return true; if (isScrambleUtil(s1, s2 + n – i, i) && isScrambleUtil(s1 + i, s2, n – i)) return true; } return false;}bool isScramble(char *s1, char *s2) { int n = strlen(s1); if (n != strlen(s2)) return false; return isScrambleUtil(s1, s2, n);}int main() { char s1[] = “great”; char s2[] = “rgeat”; printf(“Is Scramble: %s\n”, isScramble(s1, s2) ? “true” : “false”); return 0;} C++: #include <iostream>#include <string>#include <unordered_map>using namespace std;unordered_map<string, bool> memo;bool isScrambleUtil(string s1, string s2) { if (s1 == s2) return true; if (s1.size() != s2.size()) return false; string key = s1 + “#” + s2; if (memo.find(key) != memo.end()) return memo[key]; int n = s1.size(); int freq[26] = {0}; for (int i = 0; i < n; i++) { freq[s1[i] – ‘a’]++; freq[s2[i] – ‘a’]–; } for (int i = 0; i < 26; i++) { if (freq[i] != 0) return memo[key] = false; } for (int i = 1; i < n; i++) { if (isScrambleUtil(s1.substr(0, i), s2.substr(0, i)) && isScrambleUtil(s1.substr(i), s2.substr(i))) { return memo[key] = true; } if (isScrambleUtil(s1.substr(0, i), s2.substr(n – i)) && isScrambleUtil(s1.substr(i), s2.substr(0, n – i))) { return memo[key] = true; } } return memo[key] = false;}bool isScramble(string s1, string s2) { memo.clear(); return isScrambleUtil(s1, s2);}int main() { string s1 = “great”, s2 = “rgeat”; cout << “Is Scramble: ” << (isScramble(s1, s2) ? “true” : “false”) << endl; return 0;} Java: import java.util.HashMap;import java.util.Map;public class ScrambleString { 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(); int[] freq = new int[26]; for (int i = 0; i < n; i++) { freq[s1.charAt(i) – ‘a’]++; freq[s2.charAt(i) – ‘a’]–; } for (int f : freq) { if (f != 0) return memo.put(key, false); } for (int i = 1; i < n; i++) { if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) { return memo.put(key, true); } if (isScramble(s1.substring(0, i), s2.substring(n – i)) && isScramble(s1.substring(i), s2.substring(0, n – i))) { return memo.put(key, true); } } return memo.put(key, false); } public static void main(String[] args) { String s1 = “great”, s2 = “rgeat”; System.out.println(“Is Scramble: ” + isScramble(s1, s2)); }} Python: def isScramble(s1, s2): if s1 == s2: return True if sorted(s1) != sorted(s2): return False n = len(s1) for i in range(1, n): if (isScramble(s1[:i], s2[:i]) and isScramble(s1[i:], s2[i:])) or \ (isScramble(s1[:i], s2[-i:]) and isScramble(s1[i:], s2[:-i])): return True return False# Example Usages1 = “great”s2 = “rgeat”print(“Is Scramble:”, isScramble(s1, s2)) JavaScript: function isScramble(s1, s2) { if (s1 === s2) return true; if (s1.split(“”).sort().join(“”) !== s2.split(“”).sort().join(“”)) return false; let n = s1.length; for (let i = 1; i < n; i++) { if ( (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) || (isScramble(s1.substring(0, i), s2.substring(n – i)) && isScramble(s1.substring(i), s2.substring(0, n – i))) ) { return true; } } return false;}// Example Usagelet s1 = “great”;let s2 = “rgeat”;console.log(“Is Scramble:”, isScramble(s1, s2)); C# using System;using System.Collections.Generic;public class ScrambleString{ // Memoization dictionary to store previously computed results static Dictionary<string, bool> memo = new Dictionary<string, bool>(); // Helper function to check if one string is a scramble of the other public static bool IsScramble(string s1, string s2) { // If both strings are equal, no need to check further if (s1 == s2) return true; // If the lengths of the strings are not the same, return false immediately if (s1.Length != s2.Length) return false; // Create a key for memoization from the two strings string key = s1 + “#” + s2; // If the result for this pair of strings is already computed, return it if (memo.ContainsKey(key)) return memo[key]; // Check if both strings contain the same characters in the same frequency int[] freq = new int[26]; for (int i = 0; i < s1.Length; i++) { freq[s1[i] – ‘a’]++; freq[s2[i] – ‘a’]–; } // If the frequencies don’t match, they cannot be scrambles foreach (var f in freq) { if (f != 0) { memo[key] = false; // Store the result in memoization dictionary return false; } } // Now, check for the two conditions of scrambled strings: for (int i = 1; i < s1.Length; i++) { // Case 1: No swapping of substrings if (IsScramble(s1.Substring(0, i), s2.Substring(0, i)) && IsScramble(s1.Substring(i), s2.Substring(i))) { memo[key] = true; // Memoize the result return true; } // Case 2: Swapping of substrings if (IsScramble(s1.Substring(0, i), s2.Substring(s2.Length – i)) && IsScramble(s1.Substring(i), s2.Substring(0, s2.Length – i))) { memo[key] = true; // Memoize the result return true; } } // If no valid scramble was found, memoize and return false memo[key] = false; return false; } // Main function to test the scramble string function public static

Maximal Rectangle Problem The “Maximal Rectangle” problem is a classical algorithmic challenge where you are given a 2D binary matrix filled with 0‘s and 1‘s. The goal is to find the largest rectangle containing only 1‘s and return its area. Problem Statement: Given a binary matrix, find the area of the largest rectangle containing only 1s. Example: Input: matrix = [ [‘1’, ‘0’, ‘1’, ‘0’, ‘0’], [‘1’, ‘0’, ‘1’, ‘1’, ‘1’], [‘1’, ‘1’, ‘1’, ‘1’, ‘1’], [‘1’, ‘0’, ‘0’, ‘1’, ‘0’]] Output: 6 Explanation: The maximal rectangle is the rectangle with the bottom-right corner at matrix[2][2], spanning 3 columns and 2 rows. Therefore, the area is 3 * 2 = 6. Approach: Algorithm: Code Implementation in Different Languages: C: #include <stdio.h>#include <stdlib.h>int maxHistArea(int *hist, int m) { int *stack = (int *)malloc(m * sizeof(int)); int top = -1, maxArea = 0, area = 0, i = 0; while (i < m) { if (top == -1 || hist[stack[top]] <= hist[i]) { stack[++top] = i++; } else { int height = hist[stack[top–]]; int width = (top == -1) ? i : i – stack[top] – 1; area = height * width; maxArea = (maxArea > area) ? maxArea : area; } } while (top >= 0) { int height = hist[stack[top–]]; int width = (top == -1) ? i : i – stack[top] – 1; area = height * width; maxArea = (maxArea > area) ? maxArea : area; } free(stack); return maxArea;}int maximalRectangle(char **matrix, int n, int m) { int *heights = (int *)calloc(m, sizeof(int)); int maxArea = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { heights[j] = (matrix[i][j] == ‘1’) ? heights[j] + 1 : 0; } int area = maxHistArea(heights, m); maxArea = (maxArea > area) ? maxArea : area; } free(heights); return maxArea;}int main() { char *matrix[] = { “10100”, “10111”, “11111”, “10010” }; int n = 4, m = 5; printf(“Maximal Rectangle Area: %d\n”, maximalRectangle(matrix, n, m)); return 0;} C++: #include <iostream>#include <vector>#include <stack>#include <algorithm>using namespace std;int maxHistArea(vector<int>& hist, int m) { stack<int> st; int maxArea = 0, area = 0, i = 0; while (i < m) { if (st.empty() || hist[st.top()] <= hist[i]) { st.push(i++); } else { int height = hist[st.top()]; st.pop(); int width = st.empty() ? i : i – st.top() – 1; area = height * width; maxArea = max(maxArea, area); } } while (!st.empty()) { int height = hist[st.top()]; st.pop(); int width = st.empty() ? i : i – st.top() – 1; area = height * width; maxArea = max(maxArea, area); } return maxArea;}int maximalRectangle(vector<vector<char>>& matrix) { if (matrix.empty()) return 0; int n = matrix.size(), m = matrix[0].size(); vector<int> heights(m, 0); int maxArea = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { heights[j] = (matrix[i][j] == ‘1’) ? heights[j] + 1 : 0; } maxArea = max(maxArea, maxHistArea(heights, m)); } return maxArea;}int main() { vector<vector<char>> matrix = { {‘1’, ‘0’, ‘1’, ‘0’, ‘0’}, {‘1’, ‘0’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘1’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘0’, ‘0’, ‘1’, ‘0’} }; cout << “Maximal Rectangle Area: ” << maximalRectangle(matrix) << endl; return 0;} Java: import java.util.Stack;public class MaximalRectangle { public static int maxHistArea(int[] hist, int m) { Stack<Integer> stack = new Stack<>(); int maxArea = 0, area = 0, i = 0; while (i < m) { if (stack.isEmpty() || hist[stack.peek()] <= hist[i]) { stack.push(i++); } else { int height = hist[stack.pop()]; int width = stack.isEmpty() ? i : i – stack.peek() – 1; area = height * width; maxArea = Math.max(maxArea, area); } } while (!stack.isEmpty()) { int height = hist[stack.pop()]; int width = stack.isEmpty() ? i : i – stack.peek() – 1; area = height * width; maxArea = Math.max(maxArea, area); } return maxArea; } public static int maximalRectangle(char[][] matrix) { if (matrix.length == 0) return 0; int n = matrix.length, m = matrix[0].length; int[] heights = new int[m]; int maxArea = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { heights[j] = (matrix[i][j] == ‘1’) ? heights[j] + 1 : 0; } maxArea = Math.max(maxArea, maxHistArea(heights, m)); } return maxArea; } public static void main(String[] args) { char[][] matrix = { {‘1’, ‘0’, ‘1’, ‘0’, ‘0’}, {‘1’, ‘0’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘1’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘0’, ‘0’, ‘1’, ‘0’} }; System.out.println(“Maximal Rectangle Area: ” + maximalRectangle(matrix)); }} Python: def maxHistArea(heights): stack = [] max_area = 0 i = 0 while i < len(heights): if not stack or heights[stack[-1]] <= heights[i]: stack.append(i) i += 1 else: h = heights[stack.pop()] w = i if not stack else i – stack[-1] – 1 max_area = max(max_area, h * w) while stack: h = heights[stack.pop()] w = i if not stack else i – stack[-1] – 1 max_area = max(max_area, h * w) return max_areadef maximalRectangle(matrix): if not matrix: return 0 n, m = len(matrix), len(matrix[0]) heights = [0] * m max_area = 0 for i in range(n): for j in range(m): heights[j] = heights[j] + 1 if matrix[i][j] == ‘1’ else 0 max_area = max(max_area, maxHistArea(heights)) return max_area# Example Usagematrix = [ [‘1’, ‘0’, ‘1’, ‘0’, ‘0’], [‘1’, ‘0’, ‘1’, ‘1’, ‘1’], [‘1’, ‘1’, ‘1’, ‘1’, ‘1’], [‘1’, ‘0’, ‘0’, ‘1’, ‘0’]]print(“Maximal Rectangle Area:”, maximalRectangle(matrix)) C#: using System;using System.Collections.Generic;public class MaximalRectangle { public static int MaxHistArea(int[] hist, int m) { Stack<int> stack = new Stack<int>(); int maxArea = 0, area = 0, i = 0; while (i < m) { if (stack.Count == 0 || hist[stack.Peek()] <= hist[i]) { stack.Push(i++); } else { int height = hist[stack.Pop()]; int width = stack.Count == 0 ? i : i – stack.Peek() – 1; area = height * width; maxArea = Math.Max(maxArea, area); } } while (stack.Count > 0) { int height = hist[stack.Pop()]; int width = stack.Count == 0 ? i : i – stack.Peek() – 1; area = height * width; maxArea

Given an array of words, print all anagrams together. Input : {“cat”, “dog”, “tac”, “god”, “act”} Output : {“cat”, “tac”, “act”, ‘”dog”, “god”} One could start with a simple hash table creation. Determine each word’s hash value such that every anagram has the same hash value. Stow these hash values into the hash table. Print those words finally beside the same hash values. One can use a basic hash system modulo sum of ASCII values of every character. Modulo sum allows two non-anagram words to have the same hash value. This is to be managed by complementary characters. Another approach to print all the anagrams simultaneously is following. Consider two auxiliary arrays, index array, and word array. Add the specified word sequence to the word array. Sort every individual word in the word array. Sort the word array last then trace the matching indices. All the anagrams gather together following sorting. Print the strings from the original array by means of the index array. Using the following Sequence of Words, let us grasp the procedures: “cat”, “dog”, “tac”, “god”, “act” 1) Create two auxiliary arrays index[] and words[]. Copy all given words to words[] and store the original indexes in index[]  index[]: 0 1 2 3 4 words[]: cat dog tac god act 2) Sort individual words in words[]. Index array doesn’t change. index[]: 0 1 2 3 4 words[]: act dgo act dgo act 3) Sort the words array. Compare individual words using strcmp() to sort index: 0 2 4 1 3 words[]: act act act dgo dgo 4) All anagrams come together. But words are changed in the words array. To print the original words, take the index from the index array and use it in the original array. We get  “cat tac act dog god” C C++ Java Python JS

You are given a string S and a list of words L, which is essentially an array or vector of strings with all the same length. Determine the beginning indices of the substrings in string S, which has every word found in list L. If string S is “barfooapplefoobar” and list of words (L) is [“ foo”, “barfu” then we have to search for substrings “foobar,” “barfu,” in string S. The sequence of words in list L does not matter. Note: Words within the list L can be repeated. Examples : Input : S: “barfoothefoobarman” L: [“foo”, “bar”] Output : 0 9 Explanation : // at index 0 : barfoo // at index 9 : foobar Input : S: “catbatatecatatebat” L: [“cat”, “ate”, “bat”] Output : 0 3 9 Explanation : // at index 0 : catbatate // at index 3 : batatecat // at index 9 : catatebat Input : S : “abcdababcd” L : [“ab”, “ab”, “cd”] Output : 0 2 4 Explanation : // at index 0 : abcdab // at index 2 : cdabab // at index 4 : ababcd Input : S : “abcdababcd” L : [“ab”, “ab”] Output : 4 Approach : We can use Hashing Technique to solve the above problem. Let’s walk through the procedures: Declare a map (hash_map) containing every word from List L matching their occurrences within List L. Go through all conceivable substrings in string S that match size_L (total character count generated if all the words in list L concatenated). For every conceivable substring, first create a temporary map (temp_hash_map) from original map (hash_map). Get the words from the substring; if the word appears in temp_hash_map we reduce its corresponding count; if it does not appear in temp_hash_map we merely break. Following our substring, we search temp_hash_map for any key whose count exceeds 0. Should we discover no such key, all the words in list L were discovered in substring; should we discover a key whose count exceeds 0, we did not traverse the entire substring since we came across a word not in temp_hash_map. C++ Java Python3 JS Output 0 9 Time Complexity : O(N – K) * K N : length of string S. K : total length of list L if all the words are concatenated. If L : [“ab”, “cd”] then K = 4. Space Complexity:  O(K), where K : total length of list L

Allow us to grasp the answer using the example below.arr[{2, 3, 4}First we create all sequences including one digit {2}, obtaining “a,” “b,” and “c.”We then create all sequences with two digits {2, 3}, obtaining “ad,” “ae,” “af,” “bd,” “be,” “bf,” “cd,” “ce,” “cf.” We can just take all past sequences with one digit and one by one add all characters that fit three (“d”, “e“, “f”). We thus have 3 x 3 = 9 sequences.We follow the same procedure for the last digit 4 and get 9 x 3 = 27 needed sequences. The next sequence from the last one now begs the issue of how we got it. We mostly have to handle the FIFO order’s past sequence. For this reason, a queue would be absolutely ideal. We first construct result with i+1 digits by removing every item from queue and adding all characters corresponding to (i + 1)-th digit. We then queue result with i digits. The above method is applied here below: C++ C Java Python JavaScript

Roman symbol values may be kept using an unordered map. We must thus cycle through the string and for every symbol see whether the present value is less than the next value in order to solve the puzzle. If so, add the outcome of subtracting the current value from the next value to the total. Add the current value to the total otherwise. C++ Java Python Js Output 9 Time Complexity: O(N), As we have to iterate the string only once.Auxiliary Space: O(1), As we are using a map of constant size, so the space complexity becomes O(1)

The challenge is to translate a Roman string entered into roman form into an integer. The symbols I, V, X, L, C, D, and M define 1, 5, 10, 50, 100, 500, and 1,000, respectively, so Roman numerals are based on these symbols. Various ways these symbols are arranged show different numbers. Roman numerals I, II, III, IV, V, VI, VII, VIII, IX, and X correspond, respectively, 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. How did the conversion go? Should a higher value symbol precede, we deduct. In other cases, we add.In IV I precedes V, and V has a higher value—five. Our answer is thus 5 – 1 = 4.In VI, V occurs before I and I has a smaller value 1. Our answer then is 5 + 1 = 6.In II, we have equal values; so, we add and get 1 + 1 = 2.When more than two characters are involved, we move from left to right and group just when we come upon a larger value character following a lower. MXVII for instance is 1000 + 10 + 5 + 1 + 1 = 1017. XLVII also equals (50 – 10) + 5 + 1 + 1 = 47. L is bigger and comes after X, though. Example: Input: IXOutput: 9Explanation: IX is a Roman symbol which represents 10 – 1 = 9 Input: XLOutput: 40Explanation: XL is a Roman symbol which represents 50 – 10 = 40 Input: MCMIVOutput: 1904Explanation: M is 1000, CM is 1000 – 100 = 900, and IV is 4. So we have total as 1000 + 900 + 4 = 1904 Using Iterative Comparison – O(n) time and O(1) space Turning a Roman numeral into an integer requires us to walk the string from left to right. For every symbol, pair it with the following symbol—if one exists. Add the value of the current symbol to the resultant value if it is either more than or equal to the following symbol. Otherwise, skip the next symbol and subtract its value from the value of the following symbol then add the resultant total. The thorough guidelines for above intuition are found below: C++ Java Python JS Output 9 Time Complexity: O(n), where n is the length of the string. Only one traversal of the string is required.Auxiliary Space: O(1), As no extra space is required. Read More: [Expected Approach-2] Using Hashing– O(n) time and O(1) space

Examples:  Input : 9Output : IXInput : 40Output : XLInput : 1904Output : MCMIV Following is the list of Roman symbols which include subtractive cases also: SYMBOL VALUEI 1IV 4V 5IX 9X 10XL 40L 50XC 90C 100CD 400D 500CM 900 M 1000 The plan is to separately convert the tens, hundreds, thousands of sites of the specified number. There is no matching Roman numeral symbol if the digit is zero. Because these digits use subtractive notation, the conversion of digits 4’s and 9’s is somewhat different from other digits. Method for Roman numeral conversion from decimal numberComparing provided number with base values in the sequence 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1, The first base value—largest base value—will be either exactly less or equal to the specified integer.Divide the number by its highest base value; the corresponding base symbol will be repeated quotient times; the residual will then be the number for next divisions and repetitions. The cycle will be continued until the count runs zero. Example to demonstrate above algorithm:  Convert 3549 to its Roman Numerals Output:  MMMDXLIX Explanation: First step: First number = 3549Since 3549 > 1000; first base value will be 1000 initially.Get 3549/1000 divided. Remainder =549; quotient = 3. Three times will be the equivalent sign M repeated.We list the Result value in the second list.Now remainder is not equal to zero hence we call the method once more. Two steps Number now is 549; maximum base value will be 500; 1000 > 549 >= 500.Split 549/500. Remainder: 49; quotient: 1. Once, the matching symbol D will be repeated to stop the loop.We list the Result value in the second list.Now remainder is not equal to zero hence we call the method once more.The third step Number now is 49; maximum base value is 40; 50 > 49 >= 40.Sort 49/40. Quotient is one; remainder is nine. Once, the matching symbol XL will be repeated to stop the loop.We list the Result value in the second list.Now remainder is not equal to zero hence we call the method once more.Step Four Now, number is 9.List l contains number 9; so, we straight get the value from dictionary dict and set Remainder=0 and finish the loop.Remainder= 0. We shall not call the method once more since the related symbol IX will be repeated once and the remaining value is 0.Step five At last, we align with the second list values.The result came MMMDXLIX.The above method is applied following here: C++ Java Python C# Output MMMDXLIX Time Complexity: O(N), where N is the length of ans string that stores the conversion.Auxiliary Space: O(N)