Special Substrings :
Difficulty Level : Hard
Submissions : 451
Asked In :
Marks :10
: 0 | : 1
You are given a string $$$drawString$$$, $$$numTickets$$$ ticket strings, and an integer $$$tolerance$$$,
You can change each ticket by the following ways:
- Change character 'o' to character 'a' and vice versa in the ticket any number of times.
- Change character 't' to character 'l' and vice versa in the ticket any number of times.
- Erase a character from anywhere in the ticket at most one time.
A ticket is special substring if you can ignore at most $$$tolerance$$$ amount of characters from the $$$drawString$$$ to get a match with the ticket string.
You have to count the number of tickets which are special substring of $$$drawString$$$.
The first line contains an integer $$$numTickets, (0 \le numtickets \le 1000)$$$
The next $$$numtickets$$$ lines contains a string, representing $$$ticket_{i}, (0 \le |ticket_{i}| \le 200$$$
The next line contains a string $$$drawString, (0 \le |drawString| \le 200$$$
The next line contains an integer $$$tolerance, (0 \le tolerance \le 1000)$$$
Print an integer representing the number of tickets which are special substrings.
3 abcde aoc actld aabacd 1
2
6 abrrra abra codabro cadabrott caddbrott obradb abracadabral 3
4
In the first sample case:
- For the first ticket 'abcde' - delete 'e' from the ticket, and delete 'a' from the $$$drawString$$$, so the new ticket 'abcd' is a substring of the new $$$drawString$$$.
- For the second ticket 'aoc' - change 'o' to 'a' and delete 'b' from the $$$drawString$$$. So, the new ticket is the substring of the new $$$drawString$$$.
- For the third ticket, there is no way to get the ticket as the substring of the $$$drawString$$$.
So, the answer is 2.
