Header Ad

HackerRank LCS Returns problem solution

In this HackerRank LCS Returns problem solution, we have given two strings, a and b, find and print the total number of ways to insert a character at any position in the string. The length of the Longest Common Subsequence of characters in the two strings increases by one.

HackerRank LCS Returns problem solution


Problem solution in Java.

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

{"mode":"full","isActive":false}


Problem solution in C++.

#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>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Ford(i,a,b) for(int i=a;i>=b;i--)
const int N=5000+1067;
int f[N][N],f1[N][N],res;
bool check[N][N];
using namespace std;
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    string s,t;
    cin>>s;
    cin>>t;
    int n=s.length();
    int m=t.length();
    s="n"+s;
    t="n"+t;
    For(i,1,n) For(j,1,m) f[i][j]=max(max(f[i][j-1],f[i-1][j]),f[i-1][j-1]+(s[i]==t[j]));
    Ford(i,n,1) Ford(j,m,1) f1[i][j]=max(max(f1[i][j+1],f1[i+1][j]),f1[i+1][j+1]+(s[i]==t[j]));
    For(i,0,n) For(j,1,m) if (!check[i][t[j]]&&f[i][j-1]+f1[i+1][j+1]+1>f[n][m]) check[i][t[j]]=true,++res;
    cout<<res<<endl;
    return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

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

{"mode":"full","isActive":false}


Post a Comment

0 Comments