Question

Flipkart | SDE | Coding OA Questions and Solutions | Set - 3

Answer 1

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 win 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 string in order to win the lottery. To avoid any kind of suspicion, they can make the following changes in their string.

 

they can change character ‘o’ to character ‘a’ and vice versa.
They can change character ‘t’ to character ‘I’ and vice versa.
They can erase a character from anywhere in the string.
Note that they can ignore at most ‘K’ character from the 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).

 

Eg. draw string = aabacd, K=2
tickets = [abcde acmfgtld]

 

abcde -> abcd (erase a character)
abcd matches with the substring "abacd" of the draw string (after ignoring one character)
Hence, abcd will win the lottery.

Comments

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

---

public static boolean helper(String str,String s,int k,int i,int j,boolean mark){
    if(i > str.length() || j > s.length()) return false;
    if(j == s.length()){
        return true;
    }
    if(i == str.length()){
        return false;
    }
    
    char ch1 = str.charAt(i);
    char ch2 = s.charAt(j);
    
    boolean flag = false;
    
    if(ch1 == ch2 || (ch1 == 'a' && ch2 == 'o') || (ch1 == 'o' && ch2 == 'a') || (ch1 == 't' && ch2 == 'l') || (ch1 == 'l' && ch2 == 't')){
        flag = flag || helper(str,s,k,i+1,j+1,true);
    }else if(k > 0  && mark){
        flag = flag || helper(str,s,k-1,i+1,j,true);
    }
    
    if(!mark)
     flag = flag || helper(str,s,k,i+1,j,false);
    

    return flag;
}
public static int lotteryTickets(String matchStr, String[] tickets, int k) {
   
    int count = 0;
    int n = matchStr.length();

    for(String str : tickets){
        if(helper(matchStr,str,k,0,0,false)) count++;
    }
    return count;
}

---

#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);
    }
    else if(K>0 && mark==true){  //mark represents that substring has started now, and now we can use K to ignore
        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;
}