Programming Challenge Description:
A subsequence of a given sequence S consists of S with zero or more elements deleted. Formally, a sequence Z = z1z2..zk is a subsequence of X = x1x2…xm, if there exists a strictly increasing sequence of indices (i) of X such that for all j=1,2,…k we have Xi = Zj. E.g. Z=bcdb is a subsequence of X=abcbdab with corresponding index sequence <2,3,5,7>
Input:
Your program should read lines from standard input. Each line contains two comma separated strings. The first is the sequence X and the second is the subsequence Z.
Output:
Print out the number of distinct occurrences of Z in X as a subsequence.
Test 1 Test Input babgbag,bag Expected Output 5 Test 2 Test Input rabbbit,rabbit Expected Output 3
Program:
package com.emexo.programmingchallenge; import java.io.*; public class FindTheLookupforSubsequence { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s; while ((s = in.readLine()) != null) { String[] inputArray = s.split(","); String sequence = inputArray[0]; String sub = inputArray[1]; System.out.println(count(sequence, sub)); } } private static int count(String sequence, String sub) { int m = (sequence != null ? sequence.length() : 0); int n = (sequence != null ? sub.length() : 0); // Create a table to store results of sub-problems int lookup[][] = new int[m + 1][n + 1]; // If first string is empty for (int i = 0; i <= n; ++i) lookup[0][i] = 0; // If second string is empty for (int i = 0; i <= m; ++i) lookup[i][0] = 1; // Fill lookup[][] in bottom up manner for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // If last characters are same, we have two // options - // 1. consider last characters of both strings in solution // 2. ignore last character of first string if (sequence.charAt(i - 1) == sub.charAt(j - 1)) lookup[i][j] = lookup[i - 1][j - 1] + lookup[i - 1][j]; else // If last character are different, ignore // last character of first string lookup[i][j] = lookup[i - 1][j]; } } return lookup[m][n]; } }