_Binary_Search_'s blog

By _Binary_Search_, history, 2 years ago, In English

Problem Statement

The Cytes Lottery is the biggest lottery in the world. On each ticket, there is a string of a-z letters. The company produces a draw string S. A person wins if his/her ticket string is a special substring of the draw string. A special substring is a substring which can be formed by ignoring at most K characters from drawString. For example, if draw string = "xyzabc" and tickets are [ac zb yhja] with K=1 then the winning tickets will be 2 i.e ac (won by ignoring "b" in drawstring) and zb (won by ignoring "a" in drawstring).

Now some people change their ticket strings in order to win the lottery. To avoid any kind of suspicion, they can make the following changes in their strings.

They can change character 'o' to character 'a' and vice versa They can change character 't' to character 'l' and vice versa They can erase a character from anywhere in the string Note that they can ignore at most 'K' characters from the draw string to get a match with the ticket string.

Write an algorithm to find the number of people who win the lottery (either honestly or by cheating).

Input:

The first line of the input consists of an integer — numTickets, representing the number of tickets (N). The second line consists of a string — drawString, representing the draw string (S). The third line consists of N space-seperated strings — tickets1, tickets2,........., ticketsN representing the tickets.

The last line consists of an integer-tolerance, representing the maximum number of characters that can be deleted from the drawString(K).

Output:

An integer representing the number of winning tickets (either fairly or by cheating).

Constraints:

0 <= numTickets <= 1000 0 <= length of drawString <= 200 0 <= length of tickets[i] <= 200 0 <= tolerance <= 1000 Note:

The drawString contains lowercase English alphabets

Example:

Input:

3 aabacd abcde aoc actld 1 Output:

2

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any solutions for this?

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Pls solve this problem.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

They can change their character. But, it's ambiguous. How many times they can change. Is it once, or any number of times. I got this question today in Wipro OA, but wasn't able to solve fully becoz I didn't even understand it properly. You can erase a character in ticket. How many times? Once or what

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
using namespace std;

bool check(char c1, char c2){
    if(c1==c2){
        return true;
    }
    if(c1=='a' && c2=='o'){
        return true;
    }
    if(c1=='o' && c2=='a'){
        return true;
    }
    if(c1=='t' && c2=='l'){
        return true;
    }
    if(c1=='l' && c2=='t'){
        return true;
    }
    return false;
}

bool helper(string &str, string &test, int n, int m, int K, bool mark, bool deleteOnce){
    if(m==0){
        return true;
    }
    if(n==0){
        return false;
    }
    bool res=false;
    if(check(str[n-1],test[m-1])==true){  
        res=res | helper(str,test,n-1,m-1,K,true,deleteOnce);
    }
    if(K>0 && mark==true){  // mark represents that substring has started now, and now we can use K to ignore elements in this running substring
        res=res | helper(str,test,n-1,m,K-1,true,deleteOnce);
    }
    if(deleteOnce==false){  // delete once says, we can delete any character in ticket atleast once
        res=res | helper(str,test,n,m-1,K,mark,true);
    }
    if(mark==false){  // if mark is false, this means substring has not started yet, just move ahead in baseString
        res=res | helper(str,test,n-1,m,K,false,deleteOnce);
    }
    return res;
}

int main() {
    string s="aabacd";
    vector<string> str={"abcde","aoc","aabade"};
    int res=0;
    int K=2;
    for(auto e: str){
        if(helper(s,e,s.size(),e.size(),K,false,false)==true){
            res++;
        }
    }
    cout<<res;
    return 0;
}
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is time complexity of this solution?