Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
We live in a society where personality is a distant memory.
Nowadays personality is represented by strings. You are given two strings $S$ and $T$ and an integer $k$. You can apply following operation on the string $S$ at most $k$ times.
Suppose the final string after applying operations is called $X$. You have to calculate the number of distinct strings $X$ where $T$ is a subsequence of $X$ after applying at most $k$ operations on string $S$. Number of operations for each $X$ is independent $i.e$ you can apply at most $k$ operations in each time of making $X$.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none or all) of the characters without disturbing the relative positions of the remaining characters. ($i.e$ ace is a subsequence of abcde while aec is not).
The first line contains three integers $n$, $m$ and $k$ ${(1 \le n, m \le 10, 0 \le k \le 1000)}$ $$size of the string $S$, size of the string $T$ and maximum number of operations respectively.
The second line contains string $S$ containing only lowercase English letters.
The third line contains string $T$ containing only lowercase English letters.
Print a single integer $$ total number of such distinct strings $X$ where $T$ is a subsequence of $X$ after applying at most $k$ operations for each $X$.
Input  Output 

2 1 2 ab a  2 
The resulting strings are $ab$, $ba$. 
Input  Output 

2 3 1 aa aaa  0 
78% Solution Ratio
adnan_tokyEarliest,
pathanFastest, 0.2s
ashikurrahmanLightest, 131 kB
antihashShortest, 1010B
Login to submit
This problem is straightforward. Generate all permutations of SSS, check is TTT is a subsequence and...
CodeSpark 2021

Replay of CodeSpark 2021
