Lottery Ticket

Hard
0/120
Average time to solve is 45m
profile
Contributed by
5 upvotes
Asked in company
Flipkart limited

Problem statement

You are given a list of lottery tickets ‘tickets’ where each ticket is a string of lowercase characters. You are also given a match string, ‘matchStr’. A ticket will be considered a winning ticket if a substring of ‘matchStr’ is equal to the ticket by skipping at most 'K' characters of the substring.

To make more winning tickets, you can perform the following operations-:

1- Change 'a' to 'o' or vice versa
2- Change 't' to 'l' or vice versa

Your task is to find the number of winning tickets.

For example: 
You are given ‘tickets’ = [‘abcd’, ‘acmfgtld’], ‘K’ = 2, and 'matchStr' = ‘aabacd’
For the ticket ‘abcd’, is equal to the substring ‘abacd’ by skipping the third character of ‘abacd’. Hence the answer is 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of input contains two space-separated integers, ‘N’ and ‘K’, representing the number of tickets and the given integer.

The second line of each test case contains a single string, representing the match string ‘matchStr’.

The next line contains ‘N’ space-separated strings representing the ticket strings.
Output Format: 
For each test case, print a single integer representing the number of tickets that can be the winning ticket.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= N, K <= 10^3
1 <= |tickets[i]| , |matchStr| <= 500

Time Limit: 1 sec
Sample Input 1:
2
2 2
aabacd
abcd acmfgtld
3 1
akgfhdlskjes
agfh aghd kje
Sample Output 1:
1
2
Explanation:
For the first test case, ‘tickets’ = [‘abcd’, ‘acmfgtld’], ‘K’ = 2, and 'matchStr' = ‘aabacd’
For the ticket ‘abcd’, is equal to the substring ‘abacd’ by skipping the third character of ‘abacd’. 
Hence the answer is 1.

For the second test case, ‘tickets’ = [‘agfh’, ‘aghd’, ‘kje’ ], ‘K’ = 1, and 'matchStr' = ‘akgfhdlskjes’
For the ticket ‘agfh’, is equal to the substring ‘akgfh’ by skipping the second character of ‘akgfh’. 
For the ticket ‘kje’, is equal to the substring ‘kje’ without skipping any character of the substring.
Hence the answer is 2.
Sample Input 2:
2
6 2
stjqiefjodjuxyge
tjqe juye xyg ojux qejo ji 
19 3
hawesqvddegyly
l s vd wes h qvd vde aw egl svd vde y de s a d w yly h
Sample Output 2:
6
19
Hint

Try the brute force approach by traversing through each substring.

Approaches (2)
Brute Force

In this approach, we will iterate through every substring and check if any ticket in matches with the substring. If a ticket is matched, we insert it in a set to stop a ticket from being added twice.

We will create a  matchChar(char1, char2) method that will check if the characters char1 and char2 are matching or not.

We will also create a function match(matchStr, ticket), which matches a matchStr with the ticket with the given conditions

 

Algorithm:

  • In the function matchChar(char1, char2)
    • If char1 and char2 are equal return True
    • If char1 is equal to ‘a’ and char2 equals to ‘o’ or vice versa, return True
    • If char1 is equal to ‘t’ and char2 equals to ‘l’ or vice versa, return True
    • Otherwise, return False
  • In the match(matchStr, ticket, k)
    • If the length of the matchStr is smaller than the length of the ticket
      • Return false
    • Set i and j as 0
    • While i is less than the length of matchStr and j is less than length of ticket
      • If matchChar(matchStr[i], ticket[i]) is True
        • Increase j by 1
      • Increase i by 1
    • If j is less than length of the ticket
      • Return false
    • Return True if i - j is not greater than k otherwise return False
  • Initialise a variable count as 0
  • Iterate i from 0 to length of matchStr
    • Iterate j from i to length of matchStr
      • Iterate ticket from tickets
        • If ticket is not in matchedTickect and match(string[i: j + 1], ticket) is True,
          • Increment count by 1
          • Break the loop
  • Finally, return the variable count
Time Complexity

O(M^2*(N)), where N and M are the total lengths of all tickets and the length of the match string.

 

We are iterating through all the substrings of the match string which will cost O(M^2) time. For each substring, we are matching it with every ticket. Hence the overall time complexity is O(M^2*(N)).

Space Complexity

O(1).

 

Constant space is being used. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Lottery Ticket
Full screen
Console