HackerRank Abbreviation Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Abbreviation Problem Solution.

You can perform the following operations on the string, a:

  1. Capitalize zero or more of a’s lowercase letters.
  2. Delete all of the remaining lowercase letters in a.

Given two strings, a and b, determine if it’s possible to make a equal to b as described. If so, print YES on a new line. Otherwise, print NO.
For example, given a = AbcDE and b = ABDE, in a we can convert b and delete c to match b. If a = AbcDE and b = AFDE. matching is not possible because letters may only be capitalized or discarded, not changed.
Function Description
Complete the function abbreviation in the editor below. It must return either YES or
NO.
abbreviation has the following parameter(s):
a: the string to modify
b: the string to match
Input Format
The first line contains a single integer q, the number of queries.
Each of the next & pairs of lines is as follows:

  • The first line of each query contains a single string, a.
    -The second line of each query contains a single string, b.

Output Format

For each query, print YES on a new line if it’s possible to make string a equal to string b. Otherwise, print NO.

Sample Input

1
daBcd
ABC

Sample Output

YES
HackerRank Abbreviation Problem Solution
HackerRank Abbreviation Problem Solution

Abbreviation C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int f(char *a,char *b,int starta,int startb){
    if(b[startb]=='\0'){
        for(int i=starta;i<strlen(a);i++){
            if(a[i]>='A'&&a[i]<='Z')
                return 0;
        }
        return 1;
    }
    else{
        for(int i=starta;i<strlen(a);i++){
            int x=0;
            if((a[i]>='A'&&a[i]<='Z')&&(a[i]!=b[startb]))
                return 0;
            else if (b[startb]==((a[i]>='A'&&a[i]<='Z'?a[i]:a[i]-32))){
                x=f(a,b,i+1,startb+1);
                if(x)
                    return 1;
            }
        }
        return 0;
    }
}

int main() {

   int t=0;
    scanf("%d",&t);
    for(int i=0;i<t;i++){
        char a[1001];
        char b[1001];
        scanf("%s",a);
        scanf("%s",b);
       a[strlen(a)]='\0';
        b[strlen(b)]='\0';
        if(strlen(b)>strlen(a))
            printf("NO\n");
        else if(strlen(a)==strlen(b)){
            if(strcmp(a,b)==0)
            {printf("YES\n");continue;}
            else
            { printf("NO\n");continue;}
        }
        if(f(a,b,0,0))
            printf("YES\n");
        else{
            printf("NO\n");
        }
    }
    return 0;
}

Abbreviation C++ Solution

    #include <bits/stdc++.h>
    #define mp make_pair
    #define pb push_back
    #define pii pair<int,int>
    #define LL long long
    #define st first
    #define nd second
    using namespace std;
    char upper(char x){
        if(x>='a'&&x<='z')
            return (char)(x-'a'+'A');
        return x;
    }
    int main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int q;
        cin>>q;
        while(q--){
            string a,b;
            cin>>a>>b;
            int low[1005];
            memset(low,0,sizeof low);
            int j=0;
            bool ok=1;
            for(int i=0;i<a.size();++i){
                if(j<=b.size()&&upper(a[i])==b[j]){
                    if(upper(a[i])!=a[i])
                        low[j]=1;
                    else
                        low[j]=0;
                    ++j;
                }
                else if(a[i]>='A'&&a[i]<='Z'){
                    --j;
                    while(b[j]!=a[i]&&j>=0&&low[j]==1)
                        --j;
                    if(j<0||(low[j]==0)){
                        ok=0;
                        break;
                    }
                    low[j]=0;
                    ++j;
                }
               }
                if(j==b.size()&&ok)
                    cout<<"YES"<<endl;
                else
                    cout<<"NO"<<endl;
        }
    }

Abbreviation C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
    class Solution
    {
        static void Main(string[] args)
        {
            int t = int.Parse(Console.ReadLine());
            while (t-- > 0)
            {
                char[] A = Console.ReadLine().ToCharArray();
                char[] B = Console.ReadLine().ToCharArray();
                int n = A.Length;
                int m = B.Length;
                bool[,] dp = new bool[n, m];
                for (int j = 0; j < m; j++)
                {
                    bool upperFlag = false;
                    for (int i = j; i < n; i++)
                    {
                        if (A[i] == B[j] || Char.ToUpper(A[i]) == B[j])
                        {
                            if (j == 0) dp[i, j] = true;
                            if (Char.IsUpper(A[i]))
                            {
                                dp[i, j] = dp[i, j] || dp[i - 1, j - 1];
                                if (dp[i, j])
                                {
                                    if (upperFlag)
                                        dp[i, j] = false;
                                    else upperFlag = true;
                                }
                            }
                            else dp[i, j] = dp[i, j] || dp[i - 1, j - 1] || dp[i - 1, j];
                        }
                        else if (!Char.IsUpper(A[i]) && i > 0)
                            dp[i, j] = dp[i - 1, j];
                    }
                }
                if (dp[n - 1, m - 1]) Console.WriteLine("YES");
                else Console.WriteLine("NO");
            }

            Console.ReadLine();
        }
    }

Abbreviation Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'abbreviation' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts following parameters:
     *  1. STRING a
     *  2. STRING b
     */

    public static String abbreviation(String a, String b) {
        boolean[][] isValid = new boolean[a.length()+1][b.length()+1];
isValid[0][0] = true;
for (int i= 1; i <= a.length(); i++) {
   if (Character.isUpperCase(a.charAt(i - 1))) {
      isValid[i][0] = false;
   }
   else isValid[i][0] = true;
}
for (int i = 1; i <= a.length(); i++) {
   for (int j = 1; j <= b.length(); j++) {
      if (a.charAt(i-1) == b.charAt(j-1)) {
      isValid[i][j] = isValid[i-1][j-1];
      }else if (Character.toUpperCase(a.charAt(i-1))  ==    b.charAt(j-1)) {
         isValid[i][j] = isValid[i-1][j-1] || isValid[i-1][j];
      }else if (Character.isUpperCase(a.charAt(i-1))) {
         isValid[i][j] = false;
      }else {
         isValid[i][j] = isValid[i-1][j];
      }
   }
}
return isValid[a.length()][b.length()]? "YES" : "NO";
/*         HashMap<Character, Integer> ha = new HashMap<>();
        HashMap<Character, Integer> hb = new HashMap<>();
        for(char ch: b.toCharArray()){
            if(!hb.containsKey(ch)){
                hb.put(ch, 1);
            }
            else{
                int f = hb.get(ch);
                hb.replace(ch, f+1);
            }
        }
        for(char ch: a.toCharArray()){
            // B has uppercase char
            if(hb.containsKey(ch)){
                if(!ha.containsKey(ch)){
                    ha.put(ch, 1);
                }
                // add char while a has less then b
                else if(ha.get(ch) < hb.get(ch)){
                    int f = ha.get(ch);
                    ha.replace(ch, f+1);    
                }
                // can't remove uppercase char from a
                else if (ha.get(ch)+1 > hb.get(ch)) {
                    return "NO";
                }
            }
            // B has uppercase char
            else if(hb.containsKey(Character.toUpperCase(ch))){
                ch = Character.toUpperCase(ch);
                if(!ha.containsKey(ch)){
                    ha.put(ch, 1);
                }
                // add char while a has less then b
                else if(ha.get(ch) < hb.get(ch)){
                    int f = ha.get(ch);
                    ha.replace(ch, f+1);    
                }
            }
            // Not in B and can't be removed
            else if(Character.isUpperCase(ch)){
                return "NO";
            }
            // Lower case not in B is not added
        }
        System.out.println("A " + ha);
        System.out.println("B " + hb);
       for(Character ch: hb.keySet()){
           if(!ha.containsKey(ch)){
               return "NO";
           }
           else if(ha.containsKey(ch)){
               if(ha.get(ch) != hb.get(ch)){
                   return "NO";
               }
           }
       }
        return "YES"; */
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                String a = bufferedReader.readLine();

                String b = bufferedReader.readLine();

                String result = Result.abbreviation(a, b);

                bufferedWriter.write(result);
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Abbreviation JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the abbreviation function below.
function abbreviation(a, b) {
    return trySolve(a, b, 0, 0 ).filter(x => x).length > 0 ? 'YES' : 'NO';
}
function trySolve(a, b){
   
    let queue = [[a.length - 1, b.length - 1]]

    let searched = {}
    let found = false;
    while(queue.length > 0){
        let idxes = queue.pop();
        let i = idxes[0]
        let j = idxes[1]

        let outOfA = i == -1;
        let finished = outOfA;
        if(finished){
            found = found || j <= 0;
            if(j <= 0) console.log(idxes)

        }

        if(!a[i]) continue;
        let isUpper = a[i].toUpperCase() == a[i] 
        if(isUpper && a[i].toUpperCase() !== b[j]){
            continue;
        }

        if(j > -1 && a[i] !== undefined && (a[i].toUpperCase() === b[j])){

            let key = ((i - 1) + " " + (j - 1))

            if(searched[key]){
                continue;
            }

            queue.push([i - 1, j - 1])
            searched[key] = true;
        }

        let isLower = a[i] !== a[i].toUpperCase()
        //delete
        if(isLower){
            let key = (i - 1 + " " + j)
            if(searched[key]){
                continue;
            }
            searched[key] = true;
            queue.push([i - 1, j])
        }
    }

    return [found]
}



function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const q = parseInt(readLine(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const a = readLine();

        const b = readLine();

        let result = abbreviation(a, b);

        ws.write(result + "\n");
    }

    ws.end();
}

Abbreviation Python Solution

q = int(input())
for i in range(0,q):
    a = input()
    b = input()
    soFar = []
    toGo = []
    soFar.append([])
    toGo.append(list(b))
    for j in range(0, len(a)):
        c = a[j]
        e = len(soFar)
        #print("so far")
        #print(soFar)
        #print("to go")
        #print(toGo)
        k = 0
        while k < e:
            if c >= 'a' and c <= 'z':
                if len(toGo[k]) > 0 and c.upper() == toGo[k][0]:
                    ne = soFar[k][:];
                    ne.append(c.upper())
                    soFar.append(ne)
                    toGo.append(toGo[k][1:])
            if c >= 'A' and c <= 'Z':
                if len(toGo[k]) == 0 or toGo[k][0] != c:
                    soFar.pop(k)
                    toGo.pop(k)
                    k-=1
                    e-=1
                else:
                    soFar[k].append(c)
                    toGo[k].pop(0)
            k+=1
    matched = False
    for j in range(0, len(toGo)):
        if len(toGo[j]) == 0:
            matched = True
    if matched:
        print("YES")
    else:
        print("NO")
c C# C++ HackerRank Solutions java javascript python