Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Abbreviation Problem Solution

HackerRank Abbreviation Problem Solution

Posted on June 19, 2023June 19, 2023 By Yashwant Parihar No Comments on HackerRank Abbreviation Problem Solution

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

Table of Contents

  • Abbreviation C Solution
  • Abbreviation C++ Solution
  • Abbreviation C Sharp Solution
  • Abbreviation Java Solution
  • Abbreviation JavaScript Solution
  • Abbreviation Python 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 Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Inverse RMQ Problem Solution
Next Post: HackerRank Two Subarrays Problem Solution

Related Posts

HackerRank The Longest Increasing Subsequence Game Problem Solution HackerRank The Longest Increasing Subsequence c
HackerRank Animal Transport Problem Solution HackerRank Animal Transport Problem Solution C++
HackerRank Save the Prisoner! Problem Solution HackerRank Save the Prisoner! Problem Solution c
Javascript project for practice | Github User Information javascript
HackerRank Cut the sticks Problem Solution HackerRank Cut the sticks Problem Solution c
HackerRank Insertion Sort - Part 1 Problem Solution HackerRank Insertion Sort – Part 1 Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme