Append and Delete Hackerrank problem solution

Append and Delete Hackerrank

You have a string, s, of lowercase English alphabetic letters. You can perform two types of operations on s:

Append a lowercase English alphabetic letter to the end of the string.
Delete the last character in the string. Performing this operation on an empty string results in an empty string.
Given an integer, k, and two strings, s and t, determine whether or not you can convert s to t by performing exactly kof the above operations on s. If it’s possible, print Yes; otherwise, print No.

Input Format

The first line contains a string, s, denoting the initial string.
The second line contains a string, t, denoting the desired final string. The third line contains an integer, k, denoting the desired number of operations.

Constraints
1<=|s|<=100 1<=|t|<=100 1<=k<=100 s and t consist of lowercase English alphabetic letters. Output Format Print Yes if you can obtain string by performing exactly operations on ; otherwise, print No. Sample Input 0

hackerhappy
hackerrank
9
Sample Output 0

Yes
Explanation 0

We perform delete operations to reduce string s to hacker. Next, we perform append operations (i.e., r, a, n, and k), to get hackerrank. Because we were able to convert s to t by performing exactly k=9 operations, we print Yes.

Sample Input 1

aba
aba
7
Sample Output 1

Yes
Explanation 1

We perform 4 delete operations to reduce string s to the empty string (recall that, though the string will be empty after 3 deletions, we can still perform a delete operation on an empty string to get the empty string). Next, we perform 3 append operations (i.e., a, b, and a). Because we were able to convert s to t by performing exactly k=7 operations, we print Yes.

Solution
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())

int main() {
    #ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    #endif
    string s, t;
    int k;
    cin >> s >> t >> k;
    int p = 0;
    while (p < min(sz(s), sz(t)) && s[p] == t[p])
        ++p;
    int vmin;
    if (k % 2 == (sz(s) + sz(t)) % 2)
        vmin = sz(s) + sz(t) - 2 * p;
    else
        vmin = sz(s) + sz(t) + 1;
    if (k < vmin)
        cout << "No\n";
    else
        cout << "Yes\n";
}
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main(){
    string s,t;
    cin>>s>>t;
    int k;
    cin>>k;
    int a= s.length();
    int b= t.length();
    int not_match=-1;
    a--;
    b--;
    for(int i=0;i<=min(a,b);i++)
    {
    if(s[i]!=t[i]) 
    {
       not_match=i;
       break;
    }    
    }
    if(not_match!=-1)
    {
    if(a<=b)
    k=k-(2*(a-not_match+1)+(b-a));  
    else
    k=k-(2*(b-not_match+1)+(a-b));        
    }    
    else   //not_match==-1 
    k=k-abs(a-b);   
    //cout<<"k="<<k<<endl<<"not_match="<<not_match<<endl;
    if(k<0)
    cout<<"No"<<endl;
    else if(k==0)
    cout<<"Yes"<<endl;
    else
    {
    if(not_match==0)    
    cout<<"Yes"<<endl;
    else if(k%2==0)
    cout<<"Yes"<<endl;
    else
    {
    if(k>=2*b)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;    
    }    
    }    
    return 0;
}
import java.util.*;

class Solution {
    
    public static boolean solve(char[] s, char[] t, int k) {
        // We have more operations than we need to delete and rewrite the string
        if (s.length + t.length < k) {
            return true;
        }
        
        // Iterate through string matching characters
        int i = -1;
        while(i++ < Math.min(s.length, t.length) - 1) {
            if (s[i] != t[i]) {
                break;
            }
        }
        
        // The strings are the same
        if (i == s.length && s.length == t.length) {
            // if k is odd, there will always be 1 operation left over
            // else, you can delete and re-append last character to use up k operations
            return ((k & 1) == 1) ? false : true;
        }

        // Else
        // Reduce k by number of necessary deletions and insertions
        k = k - (s.length - i) - (t.length - i);

        // If k < 0 or there is an odd number of operations left over, false
        // else we need exactly k operations or the number of extra ops is even, true
        return (k < 0 || (k & 1) == 1) ? false : true;
        
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        String t = in.next();
        int k = in.nextInt();
        in.close();
        
        System.out.println( (solve(s.toCharArray(), t.toCharArray(), k))
                           ? "Yes"
                           : "No"
                           );
    }
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.