Notes

1. Name for a new company
class Result {
static int newCompanyNameLen(String company1, String company2) {
int len1 = company1.length();
int len2 = company2.length();
int[][] dp = new int[len1+1][len2+1];

for(int i=1;i<=len1;i++) {
for(int j=1;j<=len2;j++) {
if(company1.charAt(i-1)==company2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
return len1+len2-dp[len1][len2];
}
}

2. Find the severity of the network problem

class Result {
static int severityLevel(String original_str, String final_str) {
int len1 = original_str.length();
int len2 = final_str.length();

int[][] dp = new int[len1+1][len2+1];

for(int i=1;i<=len1;i++) {
for(int j=1;j<=len2;j++) {
if(original_str.charAt(i-1)==final_str.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1]+1;
} else {
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}

int X = dp[len1][len2];
int severity_level = (len1-X)+(len2-X);
return severity_level;

}
}

3. Genetic Engineering

class Result {
static int minOperations(String virus1, String virus2) {
int len1 = virus1.length();
int len2 = virus2.length();
int[][] dp = new int [len1+1][len2+1];

for(int i=0;i<=len1;i++) {
for(int j=0;j<=len2;j++) {
if(i==0) {
dp[i][j] = j;
} else if(j==0) {
dp[i][j] = i;
} else if(virus1.charAt(i-1)==virus2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
int val = Math.min(dp[i-1][j],dp[i][j-1]);
dp[i][j] = 1 + Math.min(dp[i-1][j-1],val);
}
}
}
return dp[len1][len2];
}
}

4. Install Maximum Mobile Towers

class Result {
static int maxTowers(int heights[], int N) {
int[] dp = new int[N];
dp[0] = 1;
int maxTowers = 0;

for(int i=1;i<N;i++) {
dp[i] = 1;
for(int j=0;j<i;j++) {
if(heights[i]>heights[j]) {
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
maxTowers = Math.max(maxTowers, dp[i]);
}
return maxTowers;
}
}

5. Get Maximum Productivity

class Result {
static int maxProductivity(int productivity[], int n) {
int[] dp = new int [n+1];
dp[0] = 0;

for(int i=1;i<=n;i++) {
int maxPro = 0;
for(int j=1;j<=i;j++) {
maxPro = Math.max(maxPro,productivity[j-1]+dp[i-j]);
}
dp[i] = maxPro;
}
return dp[n];
}
}

6. Bitcoin Mining Target

class Result {
static long bitcoinMining(int Bitcoins[], int N, int K) {
long[] dp = new long[K+1];
dp[0] = 1;

for(int i=0;i<N;i++) {
for(int j=Bitcoins[i];j<=K;j++) {
dp[j] += dp[j-Bitcoins[i]];
}
}
return dp[K];
}
}

7. Help Ram to get maximum energy

class Result {
static int maxEnergy(int N, int energy[], int time[], int T) {
int[][] dp = new int [N+1][T+1];
for(int i=1;i<=N;i++) {
for(int j=1;j<=T;j++) {
if(j>=time[i-1]) {
int currentEnergy = energy[i-1]+dp[i-1][j-time[i-1]];
dp[i][j] = Math.max(currentEnergy,dp[i-1][j]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[N][T];
}
}

8. No effect after reversal

class Result {
static String longestPartWithNoChange(String message) {
int maxLen = 0;
int start = 0;
int n = message.length();
boolean[][] isPalindrome = new boolean[n][n];
for(int i=0;i<n;i++) {
isPalindrome[i][i] = true;
}
for(int i=0;i<n-1;i++) {
if(message.charAt(i)==message.charAt(i+1)) {
isPalindrome[i][i+1] = true;
maxLen = 2;
start = i;
}
}

for(int i=3;i<=n;i++) {
for(int j=0;j<=n-i;j++) {
int k = j+i-1;
if(message.charAt(j)==message.charAt(k) && isPalindrome[j+1][k-1]) {
isPalindrome[j][k] = true;
if(i>maxLen) {
maxLen = i;
start = j;
}
}
}
}
return message.substring(start,start+maxLen);
}
}

9. Multi-Level Points Game

import java.util.Arrays;
class Result {
static int isPossibleToWin(int N, int points[], int P, int K) {
boolean dp[][] = new boolean[N+1][P+1];
dp[0][0] = true;

for(int i=1;i<=N;i++) {
for(int j=0;j<=P;j++) {
dp[i][j] = dp[i-1][j];
if(j>=points[i-1]) {
dp[i][j] = dp[i][j] || dp[i-1][j-points[i-1]];
}
}
}
return dp[N][P-K]?1:0;
}
}

10. Maximum Area Square


class Result {
public static int maxArea(int mat[][], int m, int n) {
int[][] dp = new int[m][n];
int maxArea = 0;

for(int i=0;i<m;i++) {
dp[i][0] = mat[i][0];
maxArea = Math.max(maxArea,dp[i][0]);
}
for(int j=0;j<n;j++) {
dp[0][j] = mat[0][j];
maxArea = Math.max(maxArea,dp[0][j]);
}

for(int i=1;i<m;i++) {
for(int j=1;j<n;j++) {
if(mat[i][j]==1) {
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
maxArea = Math.max(maxArea,dp[i][j]);
}
}
}
return maxArea*maxArea;
}
}

11. Steal Maximum Money

class Result {
static int getMaxMoney(int house[][], int m, int n) {
int[][] dp = new int [m][n];
dp[m-1][n-1] = house[m-1][n-1];

for(int i=m-2;i>=0;i--) {
dp[i][n-1] = dp[i+1][n-1] + house[i][n-1];
}
for(int i=n-2;i>=0;i--) {
dp[m-1][i] = dp[m-1][i+1] + house[m-1][i];
}

for(int i=m-2;i>=0;i--) {
for(int j=n-2;j>=0;j--) {
int val = Math.max(dp[i+1][j+1], Math.max( dp[i+1][j] , dp[i][j+1]) );
dp[i][j] = house[i][j] + val;
}
}
return dp[0][0];
}
}

12. Total ways to complete the client order

class Result {
static int totalWays(int N) {
if(N==1){
return 1;
}
if(N==2){
return 2;
}
int [][]dp=new int [2][N+1];
dp[1][1]=1;
dp[1][2]=1;
dp[0][2]=1;
for(int i=3;i<=N;i++){
dp[0][i]=dp[1][i-2];
dp[1][i]=dp[0][i-1]+dp[1][i-1];
}
return dp[0][N]+dp[1][N];
}
}

13. Fair Division Among Friends

class Result {
static int fairDivision(int prices[], int n) {
// Write your code here
int totalSum = 0;
for (int i = 0; i < n; i++) {
totalSum += prices[i];
}
int targetSum = totalSum / 2;
int[][] dp = new int[n + 1][targetSum + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= targetSum; j++) {
if (prices[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], prices[i - 1] + dp[i - 1][j - prices[i - 1]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
int sum1 = dp[n][targetSum];
int sum2 = totalSum - sum1;
return Math.abs(sum1 - sum2);
}
}