Lottery Ticket

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

In this approach, we will go through each ticket and find the minimum length substring of str, which has a subsequence ticket. If the difference between the length of the current ticket and the minimum length substring is not greater than K then the ticket could be made the winning ticket.

To match the characters, we will have to take into account the conditions that the characters ‘a’ and ‘o’ are matched and the characters ‘l’ and ‘t’ are matched.

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 minimumWindowSubstring(matchStr, subseq) which finds out the minimum substring of string that has the subsequence subseq.

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 function minimumWindowSubstring(matchStr, subseq)
  • If the length of matchStr or length of subseq equals to 0
    • Return -1
  • Set right as 0
  • Set minLength as the length of matchStr + 1
  • While right is less than the length of matchStr
    • Set tIndex as 0
      • While right is less than the length of matchStr
        • If matchChar(matchStr[right], subseq[tIndex}) is True
          • Increase tIndex by 1
        • If tIndex is equal to the length of subseq
          • Break out of the loop
        • Increase right by 1
      • If right is equal to the length of the matchStr
        • Break out of the loop
      • Set left as right
      • Set tIndex as the length of subseq - 1
      • While left is not less than 0
        • If matchChar(matchStr[left], subseq[tIndex])
          • Decrease tIndex by 1
          • If tindex is less than 0
            • Break out of the loop
          • Decrease left by 1
      • Set minLength as the minimum of minLength and right - left + 1
  • Return minLength,  if minLength is not equal to the length of string -1 otherwise return -1
• Set count equal to 0
• Iterate ticket through tickets
  • Set subLen as minimumWindowSubstring(matchStr, ticket)
  • If subLen is equal to -1, continue
  • If subLen - length of ticket is not greater than K
    • Increase count by 1
• Finally, return the count