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.

Input Format

The first line contains a single string denoting a.
The second line contains a single string denoting b.

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

LCS Returns 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;
}

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("%dn",ret);
    return 0;
}