Category: Dynamic Programming
-
Data Structures & Algorithms in Java – Strings – Minimum Window Substring
Problem: Given two strings s and t , find the minimum window substring from s which contains all the characters of the string t. For example, For the input strings s = “ADOBECODEBANC” t = “ABC” The minimum window substring in s is “BANC” The possible substrings are “ADOBEC” , “BECODEBA” , “CODEBA” and “BANC”…
-
Data Structures & Algorithms in Java – Strings – Longest Repeating Character Replacement
Problem: Given a string and a number k find the longest substring whose characters can be replaced by the most repeating character to a maximum of k times. Example: Given string = “ABAB” and k = 2 You can replace the substring “ABAB” with “BBBB” since the two A’s are not the most repeating character…
-
Data Structures & Algorithms in Java – String – Longest Substring Without Repeating Characters
Problem: Given a string , find the longest substring in the string without any repeating characters. Example: For the input abcabcbb , the longest substring is abc , so the output is 3 For the input dvdf , the longest substring is vdf , so the output is 3 Try out the solution here: https://leetcode.com/problems/longest-substring-without-repeating-characters…
-
Data Structures & Algorithms in Java – Dynamic Programming – Unique Paths
Problem: Given a 2 dimensional matrix size m * n , find the number of unique ways to reach the bottom right of the matrix from the top left of the matrix (first cell) if you can move only right or down a step at a time . That is from input[0][0] to input[m-1][n-1] For…
-
Data Structures & Algorithms in Java – Dynamic Programming – Decode Ways
Problem: If A is encoded as 1 , B as 2 and so on until Z as 26 , then find the number of ways a given encoded string can be decoded. For example: The input “121” can be decoded as 1, 2 ,1 (ABA) or 12 1(LA) or 1 21 (AU) So the output…
-
Data Structures and Algorithms in Java – Dynamic Programming – Combination Sum
Problem: Given an array of numbers and a target number , find in how many ways the numbers in the input array can be summed up to form the target number. For example, Given the input: [1,2,3] and the target 4 The output should be 7 since : 1 + 1 + 1 + 1…
-
Data Structures & Algorithms in Java – Dynamic Programming – Jump Game
Problem: Given an array of numbers which indicate how many positions maximum you can jump from that index position , find out if you can reach the end of the array from the beginning. For example: For the input [2,3,1,1,4] You can jump maximum 2 positions from index 0, 3 positions from index 1 ,…
-
Data Structures & Algorithms in Java – Dynamic Programming – House Robber II
Problem: A robber goes to rob in a series of houses built next to each other forming a circle. So the first house and last house are next to each other. The robber cannot steal from consecutive houses as it would trigger an alarm. Find the maximum money the robber can steal. Input: [2,3,2] Each…
-
Data Structures & Algorithms in Java – Dynamic Programming – House Robber
Problem: A robber goes to rob in a series of houses built next to each other. He can’t rob from two consecutive houses , this will trigger an alarm. How much maximum money can he steal ? Input: The array [1,2,3,1] represents money in each house starting from the first index. Output: Maximum amount the…
-
Datastructures & Algorithms in Java – Dynamic Programming – Word Break
Problem: Given a word , find if the word could be formed by joining words together from a given dictionary. Example: The word “datastructure” can be formed using the words from the dictionary: [“data”,”algorithms”,”structure”] So ,the output is true. For the word “breadandbiscuit” and the dictionary [“and”,”bis”,”bread”] the output is false Assumptions: The words and…
