Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Here is an example:
S = “rabbbit”, T = “rabbit”

Solution:

The problem itself is very difficult to understand. It can be stated like this:
Give a sequence S and T, how many distinct sub sequences from S equals to T?

When you see string problem that is about subsequence or matching, dynamic programming method should come to mind naturally. The key is to find the initial and changing condition.

public class Solution {
    public int numDistinct(String S, String T) {
            int m = S.length();
            int n = T.length();
            int dp[][] = new int[m+1][n+1];
            
            for(int i=0; i<=m;i++){
                dp[i][0] = 1;
            }
            
            for(int i=1; i<=m; i++){
                for(int j=1; j<=n; j++){
                    if(S.charAt(i-1) == T.charAt(j-1)){
                        dp[i][j] += dp[i-1][j]+dp[i-1][j-1];
                    }else{
                        dp[i][j] +=dp[i-1][j];
                    }
                }
            }
            return dp[m][n];
    }
}

2 Thoughts on “Distinct Subsequences

  1. RadhaKrishna on January 15, 2016 at 6:15 pm said:

    public class StringSubsequence {
    public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String S = br.readLine();
    String T = br.readLine();

    distinctSeubsequence(S,T);
    }

    private static void distinctSeubsequence(String s, String t) {
    // TODO Auto-generated method stub

    char[] first = s.toCharArray();
    char[] second = t.toCharArray();

    int flag = 0;
    int count =0;

    for(int i = 0 ; i < s.length() ; i++)
    {

    if(first[i] == second[flag])
    {
    flag++;
    }

    if(flag == t.length())
    {
    count++;
    flag=0;
    System.out.println(t + " is a subsequence String of " + s);
    }
    }

    System.out.println("Number of subsequences are : " + count);

    }

    }

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation