Dynamic Programming: Print Shortest Common Supersequence
Problem Statement: You are given 2 strings, you need to print shortest common supersequence. A super sequence is a string that has both string 1 and string 2. Example Input: str1 = “abac” str2 = “cab” Output: “cabac” Why? “cabac” is the shortest common supersequence where both the strings are present. Solution In the last […]
Dynamic Programming: Length of Shortest Common Supersequence
Problem Statement: You are given 2 strings, you need to return the length of shortest common supersequence. A super sequence is a string that has both string 1 and string 2. Example Input: str1 = “abac” str2 = “cab” Output: 5 Why? “cabac” is the shortest common supersequence where both the strings are present. Solution […]
Dynamic Programming: Print Longest Common Sub-sequence
Problem Statement: You are given 2 strings S1 and S2. You need to print the Longest Common Substring. Example Solution We need to first goto tabular approach by using Bottom Up approach. Then we start from the last cell. Then we will check if the characters are equal, we will append the variable to our […]
Dynamic Programming: Longest Common Subsequence
Problem Statement: You are given 2 strings, you need to find the longest common subsequece. Example Input: Str 1: abfgkl Str 2: abcdel Output: 3 Here we have “abl” as the longest common subsequence. Here we are not finding the substring, so there can be gaps in between. And you cannot change the relative order […]
Dynamic Programming: Minimum Number of swaps to make array increasing
Problem Statement: You are given 2 arrays, you are allowed to swap arr1[i] and arr2[i]. Elements from the same index. You need to return minimum number of swaps such that they are increasing. Example Input: arr1 = [1,3,5,4], arr2 = [1,2,3,7] Output: 1 swap arr1[3] and arr2[3], then the new sequence will be arr1 = […]
Dynamic Programming: Count the number of subset with a given difference
Problem Statement: You are given with an array and a difference. You need to count the number of subsets with a given difference. Example Input: {1, 1, 2, 3} Diff = 3 Output = 2 {1, 1} {2, 3} {1, 1, 3} {2} Solution This problem is similar to 0/1 knapsack problem. i.e for every […]
Dynamic Programming: Target Sum
Problem Statement: You are given an array and a sum, you need to either add + or – to all the array elements, so that the sum should be equal to the given sum. You need to return the count of such combination. Example Input: arr 1, 1, 2, 3 Sum = 1 Output: 3 […]
Dynamic Programming: Minimum subset difference
Problem Statement: You are given an array, you need to divide into two subsets that the difference between their sum is minimum. Example Input: arr[] = {1, 6, 11, 5} Output: 2 Subset 1 {1, 6, 5} Subset 2 {11} 12 – 11 = 1 Solution This problem is an extension to equal subset sum […]
Dynamic Programming: Count of subset sum with a given sum
Problem Statement: You are given an array and a sum,you need to find the number of subsets with that sum. Example Input: arr[] = {1, 2, 3, 3}, sum = 6 Output: 3 All the possible subsets are {1, 2, 3}, {1, 2, 3} and {3, 3} Solution This problem is similar to the parent […]
Get the sum by deleting elements from the array
Problem Statement: You are given an array, you need to delete the element at nums[i] to earn num[i]. But after every delete, you have to delete all the elements that are equal to num[i] – 1 or num[i] + 1. You need to return the max sum. Example Input: nums = [4,5,3] Output: 8 First […]