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

Table of Contents

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);
});

LCS Returns C Solution

LCS Returns C++ Solution

LCS Returns C Sharp Solution

LCS Returns Java Solution

LCS Returns JavaScript Solution

Related Posts