Java Programs with Inputs & Outputs
1. Longest Palindromic Substring
Input: "babad"
Output: "bab" (or "aba")
public class LongestPalindrome {
public static void main(String[] args) {
String s = "babad";
System.out.println(new LongestPalindrome().longestPalindrome(s)); // Output: "bab" or
"aba"
}
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
2. 0/1 Knapsack Problem (DP)
Input:
• wt = [1, 3, 4, 5]
• val = [1, 4, 5, 7]
• W=7
• n=4
Output: 9
public class Knapsack {
public static void main(String[] args) {
int[] wt = {1, 3, 4, 5};
int[] val = {1, 4, 5, 7};
int W = 7, n = 4;
System.out.println(new Knapsack().knapsack(wt, val, W, n)); // Output: 9
}
public int knapsack(int[] wt, int[] val, int W, int n) {
int[][] dp = new int[n+1][W+1];
for(int i=1; i<=n; i++) {
for(int w=1; w<=W; w++) {
if(wt[i-1] <= w) {
dp[i][w] = Math.max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
} else {
dp[i][w] = dp[i-1][w];
}
}
}
return dp[n][W];
}
}
3. Kth Largest Element in a Stream
Input:
• k=3
• Initial stream: [4, 5, 8, 2]
• Additions: 3, 5, 10, 9, 4
Output: [4, 5, 5, 8, 8, 9]
import java.util.PriorityQueue;
class KthLargest {
public static void main(String[] args) {
int k = 3;
int[] nums = {4, 5, 8, 2};
KthLargest obj = new KthLargest(k, nums);
System.out.println(obj.add(3)); // Output: 4
System.out.println(obj.add(5)); // Output: 5
System.out.println(obj.add(10)); // Output: 5
System.out.println(obj.add(9)); // Output: 8
System.out.println(obj.add(4)); // Output: 8
}
private PriorityQueue<Integer> pq;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
pq = new PriorityQueue<>();
for (int num : nums) add(num);
}
public int add(int val) {
pq.offer(val);
if (pq.size() > k) pq.poll();
return pq.peek();
}
}
4. Rotten Oranges (BFS)
Input:
[
[2,1,1],
[1,1,0],
[0,1,1]
]
Output: 4
import java.util.*;
class RottenOranges {
public static void main(String[] args) {
int[][] grid = {{2,1,1}, {1,1,0}, {0,1,1}};
System.out.println(new RottenOranges().orangesRotting(grid)); // Output: 4
}
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Queue<int[]> q = new LinkedList<>();
int fresh = 0, minutes = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) q.offer(new int[]{r, c});
if (grid[r][c] == 1) fresh++;
}
}
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty() && fresh > 0) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] cell = q.poll();
for (int[] d : dirs) {
int x = cell[0] + d[0], y = cell[1] + d[1];
if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) {
grid[x][y] = 2;
q.offer(new int[]{x, y});
fresh--;
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
}
5. Word Break Problem (DP)
Input:
• s = "leetcode"
• wordDict = ["leet", "code"]
Output: true
import java.util.*;
class WordBreak {
public static void main(String[] args) {
String s = "leetcode";
List<String> wordDict = Arrays.asList("leet", "code");
System.out.println(new WordBreak().wordBreak(s, wordDict)); // Output: true
}
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
6. Stock Buy/Sell to Max Profit
Input: [7,1,5,3,6,4]
Output: 5
class MaxProfit {
public static void main(String[] args) {
int[] prices = {7,1,5,3,6,4};
System.out.println(new MaxProfit().maxProfit(prices)); // Output: 5
}
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) minPrice = price;
else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
}
return maxProfit;
}
}
7. Pivot Index in Array
Input: [1,7,3,6,5,6]
Output: 3
class PivotIndex {
public static void main(String[] args) {
int[] nums = {1,7,3,6,5,6};
System.out.println(new PivotIndex().pivotIndex(nums)); // Output: 3
}
public int pivotIndex(int[] nums) {
int total = 0, leftSum = 0;
for (int num : nums) total += num;
for (int i = 0; i < nums.length; i++) {
if (leftSum == total - leftSum - nums[i]) return i;
leftSum += nums[i];
}
return -1;
}
}
