Check if substring from indices i to j is palindrome
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
for(int end=0; end<s.length(); end++) {
for(int start=0; start<s.length(); start++) {
if (s.charAt(start) == s.charAt(end) && (end-start < 2 || isPalindrome[start+1][end-1])) {
isPalindrome[start][end] = true;
}
}
}
You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:
“1” -> ‘A’
“2” -> ‘B’
…
“25” -> ‘Y’
“26” -> ‘Z’
However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (“2” and “5” vs “25”).
Go left to right and define memo as:
memo[i] = number of ways to decode characters until i-1
So define:
int[] memo = new int[s.length()+1];
if (s.charAt(0)==’0’) return 0; //invalid
memo[0] = 1;
memo[1] = 1;
for(int index=2; index < s.length()+1; index++) {
int previousDigit = Character.getNumericValue(s.charAt(i-1));
if (previousDigit != 0) {
//if 0 we cannot decode by itself, will be like 20, 10, etc
memo[index] += memo[index-1];
}
int combinedWithPrevious = 10*Character.getNumericValue(s.charAt(i-2))+previousDigit;
if (combinedWithPrevious >= 10 && combinedWithPrevious <= 26) {
memo[index] += memo[index-2];
}
}
return memo[s.length()];
Make this more space efficient by using just two variables to hold values of memo[index-1] and memo[index-2], like fibonacci
Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
At every location try to find max length of subsequence including this number
take max of all of them
if (nums == null || nums.length==0) return 0;
int[] memo = new int[nums.length];
Arrays.fill(memo, 1)
int result=1
for(int index=1; index < nums.length; index++) {
for(int previousIndex=1; previousIndex < index; previousIndex++) {
if (nums[previousIndex] >= nums[index]) continue;
memo[index] = Math.max(memo[index], 1+memo[previousIndex]);
}
result = Math.max(memo[index], result);
}
return result;
Word break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Input: s = “leetcode”, wordDict = [“leet”,”code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
memoize memo[i]:= true if substring upto i-1 can be segmented, and then return memo[s.length()]
Convert wordDict to a set for better lookup:
Set<String> dictionary = new HashSet<>();
for(String word: wordDict)
dictionary.add(word)</String>
boolean[] memo = new boolean[s.length()-1]
memo[0] = true
for(int index=1; index < s.length()+1; index++) {
for(int previousIndex=0; previousIndex < index; previousIndex++) {
if (memo[previousIndex]) {
if (s.substring(previousIndex, index)) {
memo[index] = true; break;
}
}
}
}
return memo[s.length()]
Palindromic substrings
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”
Treat each location as potential center for a palindrome, and expand around it until letters don’t match
if odd length: center at index
if even length, center at index and index+1
int result = 0;
for(int index=0; index<s.length(); index++) {
result += numberOfPalindromes(s, index, index);
result += numberOfPalindromes(s, index, index+1);
}
return result;
private int numberOfPalindromes(String s, int left, int right) {
int result = 0;
while(left >= 0 && right < s.length()) {
if (s.charAt(left)!=s.charAt(right)) break;
left–; right++; result++;
}
return result;
}
Longest palindromic substring
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.
Again treat each index as the potential center for a palindrome and expand around it, note the substring of such largest length
if (s==null || s.length()==0) return “”;
int startIndex=0, maxLength=1;
for(int index=0; index < s.length(); index++) {
//for odd length palindrome
int maxLengthAtIndex = getMaxLength(s, index, index);
if (maxLengthAtIndex > maxLength) { maxLength = maxLengthAtIndex; startIndex=index; }
maxLengthAtIndex = getMaxLength(s, index, index+1);
if (maxLengthAtIndex > maxLength) { maxLength = maxLengthAtIndex; startIndex=index; }
}
return s.substring(startIndex, maxLength);
private int getMaxLength(String s, int left, int right) {
int length = 0;
while(left >=0 && right <s.length()) {
if (s.charAt(left)!=s.charAt(right)) break;
length++; left–; right++;
}
return length;
}
Edit distance
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
Insert a character
Delete a character
Replace a character
Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
if word1==word2 then edit distance = 0
At an index, if word1[index]==word2[index], then move on
else, perform an operation
So let memo[i, j]:= edit distance for word1 upto index i and word2 upto index j
if word1[i]==word2[j]: memo[i,j] = memo[i-1, j-1]
if word1[i]!=word2[j]:
memo[i, j] = minimum(memo[i, j-1] (remove the letter at j) + memo[i-1, j] (remove letter at i) + memo[i-1, j-1] (replace any one character)) + 1
Base case:
if (word1.length()==0) return word2.length();
if (word2.length()==0) return word1.length();
memo:
int[][] memo = new int[word1.length()+1][word2.length()+1];
for(int index=1; index<word1.length()+1; index++) {
memo[index][0] = index;
}
for(int index=1; index<word2.length()+1; index++) {
memo[0][index] = index;
}computation:
for(int index1=1; index1<=word1.length(); index1++) {
for(int index2=1; index2<=word2.length(); index2++) {
if (word1.charAt(index1-1)==word2.charAt(index2-1)) {
memo[index1][index2] = memo[index1-1][index2-1];
} else {
memo[index1][index2] = Math.min(Math.min(memo[index1-1][index2], memo[index1][index2-1]),
memo[index1-1][index2-1])+1;
}
}
}
return memo[word1.length()][word2.length()];
Can reduce space complexity to linear by only storing the last row
Coin change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
If we know the minimum number of coins to make an amount of (amount - denomination), we need just one more coin of this denomination to make the amount, so:
coins[amount, denomination] = coins[amount-denomination] + 1
if (amount <= 0) return 0;
int[] memo = new int[amount+1];
Arrays.fill(memo, amount+1);
memo[0] = 0;
for(int index=1; index<=amount; index++) {
for(int previousIndex=0; previousIndex<coins.length; previousIndex++) {
if (coins[previousIndex] <= index) {
memo[index] = Math.min(memo[index], memo[index-coins[previousIndex]]+1);
}
}
}
if (memo[amount] > amount) {
return -1;
}
return memo[amount];
}Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
let memo[step] be the number of distinct ways to climb to the top
then: memo[step] = memp[step-1] + memo[step-2]
Space optimize to get:
int previous = 0, beforeThat = 0;
for(int index=1; index <= n; index++) {
int ways = (index<=2) ? index : previous + beforeThat;
beforeThat = previous;
previous = ways;
}
return previous;You are given two 0-indexed integer arrays of the same length present and future where present[i] is the current price of the ith stock and future[i] is the price of the ith stock a year in the future. You may buy each stock at most once. You are also given an integer budget representing the amount of money you currently have.
Return the maximum amount of profit you can make.
Input: present = [5,4,6,2,3], future = [8,5,4,3,5], budget = 10
Output: 6
Explanation: One possible way to maximize your profit is to:
Buy the 0th, 3rd, and 4th stocks for a total of 5 + 2 + 3 = 10.
Next year, sell all three stocks for a total of 8 + 3 + 5 = 16.
The profit you made is 16 - 10 = 6.
It can be shown that the maximum profit you can make is 6.
Like 0-1 knapsack, weight of each stock is present[i] and value is (future[i]-present[i])
Let memo[i, j] := be the maximum profit when we can work with the stocks up to index i and have a budget of j to work with
If we skip the stock: memo[i,j] = memo[i-1, j]
If we don’t skip it: memo[i, j] = memo[i-1, j - present(i)] + value[j] if j >= present(i)
At the end return memo[number_of_stocks, budget]
int[][] memo = new int[present.length+1][budget+1];
for(int stockIndex=0; stockIndex < present.length+1; stockIndex++) {
for(int budgetIndex=0; budgetIndex<budget+1; budgetIndex++) {
if (stockIndex==0) {
memo[stockIndex][budgetIndex] = 0;
} else {
//dont buy item
memo[stockIndex][budgetIndex] = memo[stockIndex-1][budgetIndex];
//buy if budget allows
if (budgetIndex >= present[stockIndex-1]) {
int profit = future[stockIndex-1] - present[stockIndex-1];
int profitWithItem = profit + memo[stockIndex-1][budgetIndex - present[stockIndex-1]];
memo[stockIndex][budgetIndex] = Math.max(profitWithItem, memo[stockIndex][budgetIndex]);
}
}
}
}
return memo[present.length][budget];Longest Mountain in Array
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]
Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.
Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.
Use memoDecreasing[index] = length of subarray decreasing that starts at index
memoIncreasing[index] = length of subarray increasing that ends at index
take the max of both and do a minus 1 to avoid double counting of this index in the length, only if current index can be a peak
int[] leftIncreasing = new int[arr.length];
int[] rightDecreasing = new int[arr.length];
Arrays.fill(leftIncreasing, 1);
Arrays.fill(rightDecreasing, 1);
int result=0;
for(int index=1; index < arr.length; index++) {
if (arr[index] > arr[index-1])
leftIncreasing[index] = leftIncreasing[index-1]+1;
}
for(int index=arr.length-2; index>= 0; index--) {
if (arr[index] > arr[index+1])
rightDecreasing[index] = rightDecreasing[index+1]+1;
if (leftIncreasing[index] > 1 && rightDecreasing[index] > 1)
result = Math.max(result, rightDecreasing[index]+leftIncreasing[index]-1);
}
return result;Interleaving string
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:
s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + … or t1 + s1 + t2 + s2 + t3 + s3 + …
Note: a + b is the concatenation of strings a and b.
Follow up: Could you solve it using only O(s2.length) additional memory space?
Brute force: find every interleaved string possible
- Take the current character of s1, then append to it all possible interleavings of s2 with the rest of s1, compare each such result with s3
- do vice versa with s2 and s1, and compare
- true if any of them is true
Have the recursive function be:
isInterleaved(s1, s2, index1+1, result+s1[index1], s2, index2, s3) AND
isInterleaved(s1, s2, index1, result+s2[index2], s2, index2+1, s3)
private boolean isInterleaved(String s1, String s2, String result, int index1, int index2, String s3) {
if (result.equals(s3) && index1 == s1.length() && index2 == s2.length())
return true;
boolean answer = false;
if (index1 < s1.length())
answer = answer || isInterleaved(s1, s2, result+s1.charAt(index1), index1+1, index2, s3);
if (index2 < s2.length())
answer = answer || isInterleaved(s1, s2, result+s2.charAt(index2), index1, index2+1, s3);
return answer;
}
call it with:
if (s1.length()+s2.length()!=s3.length())
return false;
return isInterleaved(s1, s2, “”, 0, 0, s3);
O(2^(m+n)) time and O(m+n) space
Interleaving string: memoization
Memoize the recursive computation
Since the final result depends only on the remaining portions of s1 and s2, and not the already processed portion.
Maintain pointers index1, index2 and index3, and memo:
memo[i, j] = null if not computed
memo[i, j] = 0 if computed and false, 1 if computed and true
private boolean isInterleaved(String s1, String s2, String result, int index1, int index2, int index3, Integer[][] memo) {
if (index1 == s1.length()) {
return s2.substring(index2).equals(result.substring(index3));
}
if (index2 == s2.length()) {
return s1.substring(index1).equals(result.substring(index3));
}
if (memo[index1][index2] != null)
return (memo[index1][index2] == 0) ? false : true;
boolean answer = false;
if (
(result.charAt(index3) == s1.charAt(index1) &&
isInterleaved(s1, s2, result, index1 + 1, index2, index3 + 1, memo)) ||
(result.charAt(index3) == s2.charAt(index2) &&
isInterleaved(s1, s2, result, index1, index2 + 1, index3 + 1, memo))
) {
answer = true;
}
memo[index1][index2] = (answer == true) ? 1 : 0;
return answer;
}Interleaving string: with tabulation
Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Iterate through array and keep track of mimimum stock price so far, and subtract from current price, update max if needed
int maxProfit = 0;
int minSoFar = Integer.MAX_VALUE;
for(int price: prices) {
if (minSoFar != Integer.MAX_VALUE) //prevent underflow for op: price - minSoFar
maxProfit = Math.max(maxProfit, price - minSoFar);
minSoFar = Math.min(minSoFar, price);
}
return maxProfit;Best Time Buy and Sell Stock II
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.
Find and return the maximum profit you can achieve.
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Note: here we can buy and sell on same day I think.
Find peaks and valleys in the graph, and sum up the difference. Consider every peak following a valley to maximize the profit.
int index=0;
int valley = prices[0];
int peak = prices[0];
int maxProfit = 0;
while(index < prices.length - 1) {
while(index < prices.length-1 && prices[index] >= prices[index+1])
index++;
valley = prices[index];
while(index < prices.length-1 && prices[index] <= prices[index+1])
index++;
peak = prices[index];
maxProfit += (peak - valley);
}
return maxProfit;Optimize by adding consistently the profit for every legit transaction (it makes profit):
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) maxprofit +=
prices[i] - prices[i - 1];
}
return maxprofit;Best Time to Buy and Sell Stock III
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Consider 4 actions:
1. buy of transaction 1 -> t1_cost: buy at minimum value
2. sell of transaction 1 -> t1_profit: sell at max next value
3. buy of transaction 2 -> t2_cost: buy at minimum value again, taking into account profit from t1
4. sell of transaction 2 -> t2_profit: total profit after the last transaction, and return this value as answer
int t1Cost = Integer.MAX_VALUE, t2Cost = Integer.MAX_VALUE;
int t1Profit = 0, t2Profit = 0;
for(int price: prices) {
t1Cost = Math.min(t1Cost, price);
t1Profit = Math.max(t1Profit, price - t1Cost);
t2Cost = Math.min(t2Cost, price - t1Profit);
t2Profit = Math.max(t2Profit, price - t2Cost);
}
return t2Profit;Best Time to Buy and Sell Stock IV
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Have a function: buySell(int currentDayIndex, int remainingTransactions, boolean holdingStock)
Three possibilities to consider every day:
1. skip the day
2. sell if holding stock
3. buy if not holding the stock, and have transactions left
private int dfs(int day, int transactionsLeft, int isHolding) {
// Base case: no more days left
if (day >= n) {
return 0;
}
// Return memoized result if already computed
if (dp[day][transactionsLeft][isHolding] != null) {
return dp[day][transactionsLeft][isHolding];
}
// Option 1: Do nothing on this day (skip to next day)
int maxProfit = dfs(day + 1, transactionsLeft, isHolding);
if (isHolding == 1) {
// Currently holding stock: can sell
// Selling completes a transaction, so transactionsLeft stays the same
maxProfit = Math.max(maxProfit,
prices[day] + dfs(day + 1, transactionsLeft, 0));
} else if (transactionsLeft > 0) {
// Not holding stock and have transactions left: can buy
// Buying starts a new transaction, so decrement transactionsLeft
maxProfit = Math.max(maxProfit,
-prices[day] + dfs(day + 1, transactionsLeft - 1, 1));
}
// Memoize and return the result
return dp[day][transactionsLeft][isHolding] = maxProfit;
}Call it as:
n = prices.length;
this.prices = prices;
// Initialize memoization array
// n days, k+1 transactions (0 to k), 2 states (0: not holding, 1: holding)
dp = new Integer[n][k + 1][2];
// Start from day 0, with k transactions available, not holding any stock
return dfs(0, k, 0);Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence’s length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.
Brute force: generate all subsequences using backtracking and check which such palindrome is longest
Let memo[i, j]:= length of longest palindromic subsequence from index i to index j
if s[i]==s[j]: memo[i, j] = 2 + memo[i+1, j-1]
if s[i] != s[j]: memo[i, j] = Math.max(memo[i+1, j], memo[i, j-1])
Base case: memo[i, i] = 1
Final answer: memo[0,n-1]
Start first index (left) right to left and move second index (right) from firstIndex+1 to last index in string
int[][] memo = new int[s.length()][s.length()];
for(int index=0; index<s.length(); index++)
memo[index][index] = 1;
for(int left = s.length()-1; left >= 0; left--) {
for(int right=left+1; right < s.length(); right++) {
if (s.charAt(left)==s.charAt(right)) {
memo[left][right] = 2 + memo[left+1][right-1];
} else {
memo[left][right] = Math.max(memo[left+1][right], memo[left][right-1]);
}
}
}
return memo[0][s.length()-1];Matchsticks to Square
You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Return true if you can make this square and false otherwise.
Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
We need to divide the array into four mutually exclusive parts, all of which has equal sum of elements.
We need to figure out what subset each element belongs to, or what the sum would be.
This is the same as: Partition to K Equal Sum Subsets problem.
Too complicated to do now.
Maximal Square
Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
Output: 4
Brute force: check all possible subsquares and take the max
DP: Find max square length that has all 1’s in it, and return the sequence of it
Let memo[i, j] := max square length from 0,0 to i,j including the value at i,j
If the value at i,j is 1, then we calculate it as minimum of memo[i-1, j], memo[i-1][j-1], and memo[i, j-1] and add 1, and take the max of all these values
if (matrix==null || matrix.length==0 || matrix[0].length==0)
return 0;
int[][] memo = new int[matrix.length+1][matrix[0].length+1];
int maxSquareLength=0;
for(int row=1; row<=matrix.length; row++) {
for(int column=1; column <= matrix[0].length; column++) {
if(matrix[row-1][column-1]=='1') {
memo[row][column] = Math.min(Math.min(memo[row-1][column], memo[row][column-1]), memo[row-1][column-1])+1;
maxSquareLength = Math.max(maxSquareLength, memo[row][column]);
}
}
}
return maxSquareLength*maxSquareLength;Since we only need values from previous row space optimize it by storing only currentRow and previousRow.
if (matrix==null || matrix.length==0 || matrix[0].length==0)
return 0;
int[] previousRow = new int[matrix[0].length+1];
int[] currentRow = new int[matrix[0].length+1];
int maxSquareLength=0;
for(int row=1; row<=matrix.length; row++) {
for(int column=1; column <= matrix[0].length; column++) {
if(matrix[row-1][column-1]=='1') {
currentRow[column] = Math.min(Math.min(previousRow[column], currentRow[column-1]), previousRow[column-1])+1;
maxSquareLength = Math.max(maxSquareLength, currentRow[column]);
}
}
previousRow = currentRow.clone();
currentRow = new int[matrix[0].length+1];
}
return maxSquareLength*maxSquareLength;Minimum Window Subsequence
Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part.
If there is no such window in s1 that covers all characters in s2, return the empty string “”. If there are multiple such minimum-length windows, return the one with the left-most starting index.
Input: s1 = “abcdebdde”, s2 = “bde”
Output: “bcde”
Explanation:
“bcde” is the answer because it occurs before “bdde” which has the same length.
“deb” is not a smaller window because the elements of s2 in the window must occur in order.
let memo[i, j] = be the starting position of the shortest substring of s1 until index i-1 that contains s2 until index j-1 as a subsequence
int[][] memo = new int[s1.length()+1][s2.length()+1];
//memo[i, j] contains starting index of the substring of s1 until index i-1 that contains s2 until index j-1 as a subsequence
for(int index1 = 1; index1 <= s1.length(); index1++) {
for(int index2=1; index2 <= s2.length(); index2++) {
if (s1.charAt(index1-1)==s2.charAt(index2-1)) {
if (index2==1) { //s2 starts here so start of subsequence
memo[index1][index2] = index1;
} else {
memo[index1][index2] = memo[index1-1][index2-1]; //continue from previous match
}
} else {
memo[index1][index2] = memo[index1-1][index2]; //check from the previous match
}
}
}
int startIndex=0, minWindowLength=s1.length()+1;
//scan for positions in s1 where we have matched all of s2
for(int index1=1; index1 <= s1.length(); index1++) {
if (s1.charAt(index1-1)==s2.charAt(s2.length()-1) && memo[index1][s2.length()] > 0) {
int windowStart = memo[index1][s2.length()] - 1;
int windowLength = index1-windowStart;
if (windowLength < minWindowLength) {
startIndex = windowStart;
minWindowLength = windowLength;
}
}
}
if (minWindowLength <= s1.length()) {
return s1.substring(startIndex, startIndex + minWindowLength);
}
return "";
