Question: BNY Mellon , Online Assessment | String Modification | Meeting Assistant | Binary Autocomplete | 14th August 2023
3
Entering edit mode

1
Entering edit mode

can anyone provide the code solutions of these problems

 

ADD COMMENTlink 15 months ago Anjali Gupta • 10
0
Entering edit mode

string modification

 

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
string s;

int dp[100005][27][5];

int rec(int i, int prev, bool matched)
{

	if (i >= n)
	{
		if (matched == 1)
			return 1e17;
		else
			return 0;
	}
	if (dp[i][prev][matched] != -1)
		return dp[i][prev][matched];

	int ans = 1e17;

	if (matched == 0)
	{

		int val = s[i] - 'a';
		//	cout << val << endl;
		int cost = abs(prev - val);

		ans = cost + rec(i + 1, prev, 1);
	}
	else
	{
		// int dum = 1e9;
		for (int j = 0; j < 26; j++)
		{
			if (j == prev)
			{

				int val = s[i] - 'a';

				int cost = abs(val - prev);
				ans = min(ans, cost + rec(i + 1, prev, 1));
			}
			else
			{
				int val = s[i] - 'a';
				int cost = abs(val - prev);
				ans = min(ans, cost + rec(i + 1, prev, 0));
			}
		}
	}
	return dp[i][prev][matched] = ans;
}
int32_t main()
{

	cin >> n;
	cin >> s;
	int ans = 1e17;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < 26; i++)
	{
		int val = s[0] - 'a';
		int cost = abs(val - i);
		//	cout << cost << endl;
		ans = min(ans, cost + rec(1, i, 0));
	}

	cout << ans << endl;
	return 0;
}

 

ADD COMMENTlink 13 months ago ------------- • 70
Entering edit mode
1

//there were some small mistakes in your code
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int dp[100005][27][5];


int rec(int i, int prev, int matched,int n,string &s) {
    if (i >= n) {
        if (matched) return 0;//if its matched we should return 0 else 1e9
        else return 1e9;
    }
    
    if (dp[i][prev][matched] != -1) return dp[i][prev][matched];
    
    int ans = 1e9;
    if (matched == 0) {
        int val = s[i] - 'a';
        int cost = abs(prev - val);
        ans = cost + min(rec(i + 1, prev, 1,n,s),rec(i + 1, val, 1,n,s)); // we can change the prev to val or val to prev so we should take min of those both
    }else{
        for (int j = 0; j < 26; j++) {
        int val = s[i] - 'a';
        
        if (j == prev) {
             int cost = abs(val - prev);
            ans = min(ans, cost + rec(i + 1, j, 1,n,s));
        } else {
             int cost = abs(val - j);  // u did val -prev for everything 
            ans = min(ans, cost + rec(i + 1, j, 0,n,s));
        }
    }
    }
    dp[i][prev][matched] = ans;
    return ans;
}

int main()
{
   string s;
   cin>>s;
   int ans=1e9;
   memset(dp, -1, sizeof(dp));
   int  n = s.size();

    for (int i = 0; i < 26; i++) {
        int val = s[0] - 'a';
        int cost = abs(val - i);
        ans = min(ans, cost + rec(1, i, 0,n,s));
    }
    cout << ans << endl;
    return 0;
   
}
 

ADD REPLYlink 12 months ago
Viswanath
• 20
Entering edit mode
0

 

 
 
ADD REPLYlink 13 months ago
Aman
• 0

Login before adding your answer.

Similar Posts
Loading Similar Posts