HackerRank LCS Returns Problem Solution

HackerRank LCS Returns Problem Solution

Posted on By Yashwant Parihar No Comments on HackerRank LCS Returns Problem Solution

In this post, we will solve HackerRank LCS Returns Problem Solution.

Given two strings, a and b, find and print the total number of ways to insert a character at any position in string a such that the length of the Longest Common Subsequence of characters in the two strings increases by one.
Input Format
The first line contains a single string denoting a.
The second line contains a single string denoting b.
Constraints
Scoring
1a,b 5000

  • Strings a and b are alphanumeric (i.e., consisting of arabic digits and/or upper and lower case English letters).
  • The new character being inserted must also be alphanumeric (i.e., a digit or upper/lower case English letter).
    Output Format
    Print a single integer denoting the total number of ways to insert a character into string a in such a way that the length of the longest common subsequence of a and b increases by
    one.

Sample Input

aa
baaa

Sample Output

4
HackerRank LCS Returns Problem Solution
HackerRank LCS Returns Problem Solution

LCS Returns C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int d1[5002][5002];
int d2[5002][5002];
char s1[6000],s2[6000];
int cc[256];

int main() {
    int i,j,l1,l2,p,c,ret=0;
    scanf("%s %s",s1,s2);
    l1=strlen(s1),l2=strlen(s2);
    for(i=1;i<=l1;i++) for(j=1;j<=l2;j++) {
        d1[i][j]=d1[i-1][j];
        if (d1[i][j-1]>d1[i][j]) d1[i][j]=d1[i][j-1];
        if (s1[i-1]==s2[j-1]) d1[i][j]=d1[i-1][j-1]+1;
    }
    for(i=l1-1;i>=0;i--) for(j=l2-1;j>=0;j--) {
        d2[i][j]=d2[i+1][j];
        if (d2[i][j+1]>d2[i][j]) d2[i][j]=d2[i][j+1];
        if (s1[i]==s2[j]) d2[i][j]=d2[i+1][j+1]+1;
    }
    for(i=0;i<=l1;i++) {
        for(j=0;j<l2;j++) if (d1[i][j]+d2[i][j+1]==d1[l1][l2]) cc[s2[j]]=1;
        for(j=0;j<128;j++) if (cc[j]) ret++,cc[j]=0;
    }
    printf("%d\n",ret);
    return 0;
}

LCS Returns C++ Solution

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <sstream>
#include <ctime>
#include <memory.h>
#include <assert.h>
#include <unordered_map>
#include <limits.h>
#include <bitset>
#include <unordered_set>
using namespace std;

const long long bs = 1000000007;

static const int INF = 0x3f3f3f3f; 
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int> > vvi;

#define REP(i, n) for (int i=0; i < (int)(n); ++i)
#define pb push_back
#define mp make_pair

struct cmp {
  bool operator()(int &a, int &b) { return a < b; }
};

template<typename T>
string sv(vector<T> &v) {
  if (v.size() == 0) return "[]";
  stringstream ss;
  ss << "[";
  for (std::size_t i = 0; i < v.size() - 1; ++i) ss << v[i] << ", ";
  ss << v[v.size() - 1] << "]";
  return ss.str();
}

template<typename T>
void sv2d(vector<vector<T>> &v) {
  for (int i = 0; i < v.size(); i++) cout << sv(v[i])  << i+1 << " " << endl;
}

string a,b;

void dfs(vvi &dp, vvi &trace, int i, int j) {
  if (i == 0 || j == 0) {
    //trace[i][j]=0;
    return;
  }


  if (a[i-1] == b[j-1] && trace[i-1][j-1] != 1 ) {
    trace[i-1][j-1] = 1;
    dfs(dp,trace,i-1,j-1);
  }
  if (dp[i-1][j] == dp[i][j] && trace[i-1][j] != 1) {
    trace[i-1][j] = 1;
    dfs(dp,trace,i-1,j);
  }
  if (dp[i][j-1] == dp[i][j]  && trace[i][j-1] != 1) {
    trace[i][j-1] = 1;
    dfs(dp,trace,i,j-1);
  }
}

int main() {
  string tmp;
  cin>>tmp>>b;

  a.resize(tmp.size()*2);
  for (int i = 0; i < tmp.size(); i++) {
    a[i*2]= '_';
    a[i*2+1] = tmp[i];
  }

  vvi dp(a.size()+1, vi(b.size()+1, 0));
  vvi trace(a.size()+1, vi(b.size()+1, 0));

  unordered_set<int> cs;
  REP(i,b.size()) cs.insert(b[i]);

  int lcs = 0;
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < b.size(); j++) {
      if (a[i]==b[j]) {
        dp[i+1][j+1] = dp[i][j]+1;
        lcs = max(lcs, dp[i+1][j+1]);
        //dp[i+1][j+1] = dp[i+1][j]+1;
      } else {
        dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
        //dp[i+1][j+1] = dp[i+1][j];
      }
    }
  }

  //sv2d(dp); cout << endl;
  dfs(dp,trace,dp.size()-1,dp[0].size()-1);
  //sv2d(trace);

  //cout << endl;
  int ans = 0;

  for (auto &c : cs) {
    vector<bool>memo(dp.size());
    for (int j = 0; j < b.size(); j++) {
      if (b[j] != c) continue;
      for (int i = 0; i < a.size(); i++) {
        if (i%2!=0) continue;
        if (memo[i]) continue;
        if (trace[i+1][j+1] == 1 && dp[i+1][j+1]==dp[i+1][j]) {
          ans++;
          memo[i] = true;
        }
      }
    }

    for (int j = 0; j < b.size(); j++) {
      if (b[j] != c) continue;
      if (trace[a.size()][j]==1) {
        ans++;
        break;
      }
    }

  }


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

LCS Returns C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

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

    public static int tutzkiAndLcs(string a, string b)
        {
            int res = 0;
            int n = a.Length, m = b.Length;

            int[][] dpp = new int[n + 1][];
            int[][] dps = new int[n + 1][];

            for (int i = 0; i <= n; i++)
            {
                dpp[i] = new int[m + 1];
                dps[i] = new int[m + 1];
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (a[i] == b[j]) dpp[i + 1][j + 1] = dpp[i][j] + 1;
                    else dpp[i + 1][j + 1] = Math.Max(dpp[i][j + 1], dpp[i + 1][j]);
                }
            }
            for (int i = n - 1; i >= 0; i--)
            {
                for (int j = m - 1; j >= 0; j--)
                {
                    if (a[i] == b[j]) dps[i][j] = dps[i + 1][j + 1] + 1;
                    else dps[i][j] = Math.Max(dps[i][j + 1], dps[i + 1][j]);
                }
            }

            int r = dpp[n][m];

            bool[] bl;
            int cur;

            for (int i = 0; i <= n; i++)
            {
                bl = new bool[256];
                for (int j = 0; j < m; j++)
                {
                    if (bl[b[j]]) continue;

                    cur = dpp[i][j] + dps[i][j + 1];
                    if (r == cur)
                    {
                        res++;
                        bl[b[j]] = true;
                    }


                }
            }
            return res;
        }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string a = Console.ReadLine();

        string b = Console.ReadLine();

        int result = Result.tutzkiAndLcs(a, b);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

LCS Returns Java Solution

import java.io.*;
import java.util.*;

public class LCSReturns {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;

    void solve() throws IOException {
        String a = nextToken();
        String b = nextToken();

        int n = a.length();
        int m = b.length();

        int[][] pref = new int[n + 1][m + 1];
        int[][] suff = new int[n + 1][m + 1];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    pref[i + 1][j + 1] = pref[i][j] + 1;
                } else {
                    pref[i + 1][j + 1] = Math.max(pref[i + 1][j],
                            pref[i][j + 1]);
                }
            }

        for (int i = n - 1; i >= 0; i--)
            for (int j = m - 1; j >= 0; j--) {
                if (a.charAt(i) == b.charAt(j)) {
                    suff[i][j] = suff[i + 1][j + 1] + 1;
                } else {
                    suff[i][j] = Math.max(suff[i][j + 1], suff[i + 1][j]);
                }
            }
        
        int cur = pref[n][m];
        
        int ret = 0;

        for (int i = 0; i <= n; i++) {
            boolean[] used = new boolean[256];
            for (int j = 0; j < m; j++) {
                if (used[b.charAt(j)]) {
                    continue;
                }
                
                int now = pref[i][j] + suff[i][j + 1] + 1;
                if (now == cur + 1) {
                    used[b.charAt(j)] = true;
                    ret++;
                }
            }
        }
        
        out.println(ret);
    }

    LCSReturns() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new LCSReturns();
    }

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}

LCS Returns JavaScript Solution

function processData(input) {
    var inputStrings = input.split('\n');

    var A = inputStrings[0];
    var B = inputStrings[1];

    var lcsPrefixes = lcs(A, B);
    var lcsSuffixes = lcs(A.split('').reverse().join(''), B.split('').reverse().join(''));

    var numberOfSolutions = insertionSolutionsIncreasingLcsLengthByOne(lcsPrefixes, lcsSuffixes, B);

    console.log(numberOfSolutions);

    function lcs(a, b) {
        var A = a.split('');
        var B = b.split('');

        A.unshift(null);
        B.unshift(null);

        var rows = A.length;
        var columns = B.length;

        var lcsMatrix = matrix(rows, columns);

        for (var i = 0; i < rows; ++i) {
            for (var j = 0; j < columns; ++j) {
                var value;

                if (i == 0 || j == 0) {
                    value = 0;
                } else if (A[i] == B[j]) {
                    value = lcsMatrix[i - 1][j - 1] + 1;
                } else {
                    value = Math.max(lcsMatrix[i][j - 1], lcsMatrix[i - 1][j]);
                }

                lcsMatrix[i][j] = value;
            }
        }

        return lcsMatrix;

        function matrix(rows, columns) {
            var matrix = [];
            for (var i = 0; i < rows; ++i) {
                var rowBuffer = new ArrayBuffer(columns * 2);
                matrix[i] = new Int16Array(rowBuffer);
            }
            return matrix;
        }
    }


    function insertionSolutionsIncreasingLcsLengthByOne(lcsPrefixes, lcsSuffixes, insertionSource) {
        var numberOfRows = lcsPrefixes.length;
        var numberOfColumns = lcsPrefixes[0].length;
        var targetLength = lcsPrefixes[numberOfRows - 1][numberOfColumns - 1] + 1;

        var B = insertionSource.split('');
        B.unshift(null);

        var numberOfSolutions = 0;

        for (var i = 1; i <= numberOfRows; ++i) {
            var solutions = [];

            for (var j = 1; j < B.length; ++j) {
                var lcsLengthOfPrefixes = lcsPrefixes[i - 1][j - 1];
                var lcsLengthOfSuffixes = i < numberOfRows ?
                    lcsSuffixes[numberOfRows - i][numberOfColumns - (j + 1)] :
                    0;

                var lcsLength = lcsLengthOfPrefixes + 1 + lcsLengthOfSuffixes;

                if (lcsLength == targetLength) {
                    addSolutionToList(B[j], solutions);
                } else if (lcsLength > targetLength) {
                    removeSolutionFromList(B[j], solutions);
                }
            }

            numberOfSolutions += solutions.length;
        }

        return numberOfSolutions;

        function addSolutionToList(solution, list) {
            list.indexOf(solution) < 0 && list.push(solution);
        }

        function removeSolutionFromList(solution, list) {
            var solutionIndex = list.indexOf(solution);
            solutionIndex >= 0 && list.splice(solutionIndex, 1);
        }
    }
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
    processData(_input);
});
c, C#, C++, HackerRank Solutions, java, javascript Tags:, , , , ,

Related Posts

HackerRank Jumping on the Clouds: Revisited Problem Solution HackerRank Jumping on the Clouds: Revisited c
HackerRank Save the Prisoner! Problem Solution HackerRank Save the Prisoner! Problem Solution c
HackerRank Luck Balance Problem Solution HackerRank Luck Balance Problem Solution c
HackerRank Modified Kaprekar Numbers Problem Solution HackerRank Modified Kaprekar Numbers Solution c
HackerRank Utopian Tree Problem Solution HackerRank Utopian Tree Problem Solution c
HackerRank Insertion Sort Advanced Analysis Problem Solution HackerRank Insertion Sort Advanced Analysis c

Leave a Reply

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