CountingCommonSubsequences | Topcoder Archive

Problem Statement

A subsequence of a string is obtained by removing zero or more characters from it. You are given three Strings, and must determine the number of different non-empty subsequences they all share.

Definition

Class:: CountingCommonSubsequences
Method:: countCommonSubsequences
Parameters:: String, String, String
Returns:: long
Method signature:: long countCommonSubsequences(String a, String b, String c)
(be sure your method is public)

Notes

A subsequence should be counted only once even if it can be obtained in more than 1 way from any of the input Strings.

Constraints

a, b and c will have between 1 and 50 characters each, inclusive.
Every character of a, b and c will be a lowercase letter ('a'-'z').

Examples

```
"call"
```
```
"accelerate"
```
```
"candle"
```
```
Returns: 6
```
The 6 subsequences common to all of the strings are: "c", "a", "l", "al", "ca" and "cl".
```
"topcoder"
```
```
"topcoder"
```
```
"topcoder"
```
```
Returns: 239
```
All possible subsequences are shared by all three strings. Note that the letter 'o' is repeated, so some of the subsequences may be formed in multiple ways. Each unique subsequence is only counted once.
```
"no"
```
```
"correct"
```
```
"answer"
```
```
Returns: 0
```
There are many subsequences that are shared by any two of these strings, but none that are shared by all three of them.

"aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb"

"abababababababababababababababababababab"

"aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb"

Returns: 1725660

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.