1.
Decode Ways
import [Link].*;
public class DecodeWays {
public static int numDecodings(String s) {
if (s == null || [Link]() == 0 || [Link](0) == '0')
return 0;
int n = [Link]();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int oneDigit = [Link](i - 1) - '0';
int twoDigit = [Link]([Link](i - 2, i));
if (oneDigit >= 1)
dp[i] += dp[i - 1];
if (twoDigit >= 10 && twoDigit <= 26)
dp[i] += dp[i - 2];
return dp[n];
public static void main(String[] args) {
[Link](numDecodings("226")); // Output: 3
}
}
2. Decode Ways II
public class DecodeWaysII {
public int numDecodings(String s) {
long mod = 1000000007;
long prev2 = 1, prev1 = ways([Link](0));
for (int i = 1; i < [Link](); i++) {
long curr = (ways([Link](i)) * prev1 +
ways([Link](i - 1), [Link](i)) * prev2) % mod;
prev2 = prev1;
prev1 = curr;
return (int) prev1;
private int ways(char c) {
if (c == '*') return 9;
if (c == '0') return 0;
return 1;
private int ways(char c1, char c2) {
if (c1 == '*' && c2 == '*') return 15;
if (c1 == '*') return (c2 <= '6') ? 2 : 1;
if (c2 == '*') {
if (c1 == '1') return 9;
if (c1 == '2') return 6;
return 0;
int num = (c1 - '0') * 10 + (c2 - '0');
return (num >= 10 && num <= 26) ? 1 : 0;
}
}
3. Longest Palindromic Substring
public class LongestPalSubstring {
public static String longestPalindrome(String s) {
if (s == null || [Link]() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < [Link](); i++) {
int len1 = expand(s, i, i);
int len2 = expand(s, i, i + 1);
int len = [Link](len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
return [Link](start, end + 1);
}
private static int expand(String s, int left, int right) {
while (left >= 0 && right < [Link]() &&
[Link](left) == [Link](right)) {
left--;
right++;
return right - left - 1;
public static void main(String[] args) {
[Link](longestPalindrome("babad"));
}
}
4. Longest Palindromic Subsequence
public class LongestPalSubsequence {
public static int longestPalindromeSubseq(String s) {
int n = [Link]();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if ([Link](i) == [Link](j))
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = [Link](dp[i + 1][j], dp[i][j - 1]);
return dp[0][n - 1];
}
public static void main(String[] args) {
[Link](longestPalindromeSubseq("bbbab")); // 4
5. Maximum Subarray (Kadane’s Algorithm)
public class MaximumSubarray {
public static int maxSubArray(int[] nums) {
int maxSum = nums[0];
int current = nums[0];
for (int i = 1; i < [Link]; i++) {
current = [Link](nums[i], current + nums[i]);
maxSum = [Link](maxSum, current);
return maxSum;
public static void main(String[] args) {
int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
[Link](maxSubArray(nums)); // 6
6. Maximum Product Subarray
public class MaxProductSubarray {
public static int maxProduct(int[] nums) {
int max = nums[0];
int min = nums[0];
int result = nums[0];
for (int i = 1; i < [Link]; i++) {
int curr = nums[i];
if (curr < 0) {
int temp = max;
max = min;
min = temp;
max = [Link](curr, max * curr);
min = [Link](curr, min * curr);
result = [Link](result, max);
return result;
}
public static void main(String[] args) {
int[] nums = {2, 3, -2, 4};
[Link](maxProduct(nums)); // 6
}
}
7. Longest Turbulent Subarray
public class TurbulentSubarray {
public static int maxTurbulenceSize(int[] arr) {
int up = 1, down = 1, result = 1;
for (int i = 1; i < [Link]; i++) {
if (arr[i] > arr[i - 1]) {
up = down + 1;
down = 1;
} else if (arr[i] < arr[i - 1]) {
down = up + 1;
up = 1;
} else {
up = down = 1;
result = [Link](result, [Link](up, down));
return result;
public static void main(String[] args) {
int[] arr = {9,4,2,10,7,8,8,1,9};
[Link](maxTurbulenceSize(arr));
}
}
8. Best Time to Buy & Sell Stock (Single Transaction)
public class Stock1 {
public static int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int profit = 0;
for (int price : prices) {
minPrice = [Link](minPrice, price);
profit = [Link](profit, price - minPrice);
return profit;
public static void main(String[] args) {
int[] prices = {7,1,5,3,6,4};
[Link](maxProfit(prices)); // 5
9. Best Time to Buy & Sell Stock II (Multiple Transactions)
public class Stock2 {
public static int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < [Link]; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
return profit;
public static void main(String[] args) {
int[] prices = {7,1,5,3,6,4};
[Link](maxProfit(prices)); // 7
10. Best Time to Buy & Sell Stock with Cooldown
public class StockCooldown {
public static int maxProfit(int[] prices) {
int buy = -prices[0];
int sell = 0;
int cooldown = 0;
for (int i = 1; i < [Link]; i++) {
int prevBuy = buy;
int prevSell = sell;
buy = [Link](buy, cooldown - prices[i]);
sell = [Link](sell, prevBuy + prices[i]);
cooldown = prevSell;
}
return sell;
public static void main(String[] args) {
int[] prices = {1,2,3,0,2};
[Link](maxProfit(prices)); // 3
}
}
11. Best Time to Buy & Sell Stock III (Max 2 Transactions)
public class StockIII {
public static int maxProfit(int[] prices) {
int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
int sell1 = 0, sell2 = 0;
for (int price : prices) {
buy1 = [Link](buy1, -price);
sell1 = [Link](sell1, buy1 + price);
buy2 = [Link](buy2, sell1 - price);
sell2 = [Link](sell2, buy2 + price);
}
return sell2;
public static void main(String[] args) {
int[] prices = {3,3,5,0,0,3,1,4};
[Link](maxProfit(prices)); // 6
12. Maximal Square
public class MaximalSquare {
public static int maximalSquare(char[][] matrix) {
int m = [Link], n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
int max = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = [Link](
[Link](dp[i - 1][j], dp[i][j - 1]),
dp[i - 1][j - 1]
) + 1;
max = [Link](max, dp[i][j]);
}
return max * max;
}
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'}
};
[Link](maximalSquare(matrix)); // 4
13. Word Break
import [Link].*;
public class WordBreak {
public static boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[[Link]() + 1];
dp[0] = true;
for (int i = 1; i <= [Link](); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && [Link]([Link](j, i))) {
dp[i] = true;
break;
return dp[[Link]()];
public static void main(String[] args) {
String s = "leetcode";
List<String> dict = [Link]("leet", "code");
[Link](wordBreak(s, dict)); // true
14. Coin Change
import [Link].*;
public class CoinChange {
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
[Link](dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] = [Link](dp[i], dp[i - coin] + 1);
return dp[amount] > amount ? -1 : dp[amount];
public static void main(String[] args) {
int[] coins = {1,2,5};
[Link](coinChange(coins, 11)); // 3
15. Regular Expression Matching
public class RegexMatching {
public static boolean isMatch(String s, String p) {
int m = [Link](), n = [Link]();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++) {
if ([Link](j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if ([Link](j - 1) == '.' ||
[Link](i - 1) == [Link](j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else if ([Link](j - 1) == '*') {
dp[i][j] = dp[i][j - 2];
if ([Link](j - 2) == '.' ||
[Link](j - 2) == [Link](i - 1)) {
dp[i][j] |= dp[i - 1][j];
return dp[m][n];
public static void main(String[] args) {
[Link](isMatch("aab", "c*a*b")); // true
16. Minimum Path Sum
public class MinimumPathSum {
public static int minPathSum(int[][] grid) {
int m = [Link], n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// first row
for (int j = 1; j < n; j++)
dp[0][j] = dp[0][j - 1] + grid[0][j];
// first column
for (int i = 1; i < m; i++)
dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
int[][] grid = {
{1,3,1},
{1,5,1},
{4,2,1}
};
[Link](minPathSum(grid)); // 7
17. Longest String Chain
import [Link].*;
public class LongestStringChain {
public static int longestStrChain(String[] words) {
[Link](words, [Link](String::length));
Map<String, Integer> dp = new HashMap<>();
int max = 1;
for (String word : words) {
int best = 1;
for (int i = 0; i < [Link](); i++) {
String prev = [Link](0, i) + [Link](i + 1);
best = [Link](best, [Link](prev, 0) + 1);
[Link](word, best);
max = [Link](max, best);
}
return max;
public static void main(String[] args) {
String[] words = {"a","b","ba","bca","bda","bdca"};
[Link](longestStrChain(words)); // 4
}
}
18. Largest Sum of Averages
public class LargestSumOfAverages {
public static double largestSumOfAverages(int[] nums, int k) {
int n = [Link];
double[] prefix = new double[n + 1];
for (int i = 0; i < n; i++)
prefix[i + 1] = prefix[i] + nums[i];
double[][] dp = new double[n + 1][k + 1];
for (int i = 1; i <= n; i++)
dp[i][1] = prefix[i] / i;
for (int p = 2; p <= k; p++) {
for (int i = p; i <= n; i++) {
for (int j = p - 1; j < i; j++) {
dp[i][p] = [Link](dp[i][p],
dp[j][p - 1] + (prefix[i] - prefix[j]) / (i - j));
return dp[n][k];
public static void main(String[] args) {
int[] nums = {9,1,2,3,9};
[Link](largestSumOfAverages(nums, 3)); // 20.0
19. Longest Arithmetic Subsequence
import [Link].*;
public class LongestArithmeticSubsequence {
public static int longestArithSeqLength(int[] nums) {
int n = [Link];
Map<Integer, Integer>[] dp = new HashMap[n];
for (int i = 0; i < n; i++)
dp[i] = new HashMap<>();
int max = 2;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j];
int len = dp[j].getOrDefault(diff, 1) + 1;
dp[i].put(diff, len);
max = [Link](max, len);
}
}
return max;
public static void main(String[] args) {
int[] nums = {3,6,9,12};
[Link](longestArithSeqLength(nums)); // 4
20. Maximum Length of Repeated Subarray
public class MaxRepeatedSubarray {
public static int findLength(int[] nums1, int[] nums2) {
int m = [Link], n = [Link];
int[][] dp = new int[m + 1][n + 1];
int max = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
max = [Link](max, dp[i][j]);
return max;
public static void main(String[] args) {
int[] a = {1,2,3,2,1};
int[] b = {3,2,1,4,7};
[Link](findLength(a, b)); // 3
21. Longest Increasing Subsequence (LIS)
import [Link].*;
public class LIS {
public static int lengthOfLIS(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int num : nums) {
int idx = [Link](list, num);
if (idx < 0) idx = -(idx + 1);
if (idx == [Link]())
[Link](num);
else
[Link](idx, num);
return [Link]();
public static void main(String[] args) {
int[] nums = {10,9,2,5,3,7,101,18};
[Link](lengthOfLIS(nums)); // 4
22. Word Break (again, but clean version)
import [Link].*;
public class WordBreak {
public static boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[[Link]() + 1];
dp[0] = true;
for (int i = 1; i <= [Link](); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && [Link]([Link](j, i))) {
dp[i] = true;
break;
return dp[[Link]()];
public static void main(String[] args) {
String s = "applepenapple";
List<String> dict = [Link]("apple", "pen");
[Link](wordBreak(s, dict)); // true
23. Increasing Triplet Subsequence
public class IncreasingTriplet {
public static boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int num : nums) {
if (num <= first) {
first = num;
} else if (num <= second) {
second = num;
} else {
return true; // found third > second > first
return false;
}
public static void main(String[] args) {
int[] nums = {2,1,5,0,4,6};
[Link](increasingTriplet(nums)); // true
24. Maximum Length of Pair Chain
import [Link].*;
public class PairChain {
public static int findLongestChain(int[][] pairs) {
[Link](pairs, (a, b) -> a[1] - b[1]);
int count = 1;
int end = pairs[0][1];
for (int i = 1; i < [Link]; i++) {
if (pairs[i][0] > end) {
count++;
end = pairs[i][1];
return count;
public static void main(String[] args) {
int[][] pairs = {{1,2},{2,3},{3,4}};
[Link](findLongestChain(pairs)); // 2
25. Number of Longest Increasing Subsequence
import [Link].*;
public class NumberOfLIS {
public static int findNumberOfLIS(int[] nums) {
int n = [Link];
int[] length = new int[n];
int[] count = new int[n];
[Link](length, 1);
[Link](count, 1);
int maxLen = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (length[j] + 1 > length[i]) {
length[i] = length[j] + 1;
count[i] = count[j];
} else if (length[j] + 1 == length[i]) {
count[i] += count[j];
maxLen = [Link](maxLen, length[i]);
int result = 0;
for (int i = 0; i < n; i++) {
if (length[i] == maxLen)
result += count[i];
return result;
public static void main(String[] args) {
int[] nums = {1,3,5,4,7};
[Link](findNumberOfLIS(nums)); // 2
}