CareerCup

/* Extract all integers from string */
#include <iostream> 
#include <sstream> 
#include <bits/stdc++.h> 

using namespace std; 

string getSubString(string str, map<char, int> &m, int k)
{
    int needed = k;
    int count = 0;
    int start = 0;
    int end   = 1;
    int minLen = str.size()+1;
    int minStart = 0;
    int minEnd = 0;
    
    if (m[str[start]] == 0) {
        count++;
    }
    
    while(end != str.size()) {
        if (m[str[end]] == 0) {
            count++;
        }
        while(needed <= count && start < end) {
            if (m[str[start]] == 1){
                start++;
            }
            else if (needed < count && m[str[start]] == 0) {
                count--;
                start++;    
            }
            else {
                break;
            }
        }
        if(needed == count && minLen > (end - start + 1)) {
            minLen = (end - start + 1);
            minStart = start;
            minEnd = end;
        }
        end++;
    }
    
    return str.substr(minStart, (minEnd - minStart +1));
}

// Driver code 
int main() 
{ 
	string str = "abcdebdac"; 
	map<char, int> m;
	m['a'] = 1;
	m['b'] = 0;
	m['c'] = 1;
	m['d'] = 0;
	m['e'] = 1;
	m['f'] = 1;
	m['g'] = 1;
	m['h'] = 1;
	m['i'] = 1;
	m['j'] = 1;
	m['k'] = 1;
	m['l'] = 1;
	cout << getSubString(str, m, 2) << endl; 
	return 0; 
}

what about :
101
110
001

Can you please explain with example.

we need to find out which player to be choose..suppose if we choose 1st player then it will give ans 3 and if we choose 2nd or 3rd player it will give ans 2.now for an another ex:
101
100
010
011
if we choose 1st or 2nd player it will give ans 2 but for 3rd it is 3.

same solution i had already try but doesn't work for input:
101
001
010
110

for
101
001
010
110
it give 2 2 2 now we need to decide which one to select hear it must second or third column.
for
101
100
010
011

and here must be first or second column so.

how do you get to know which player is essential.

bool match(char *first, char * second)
{
    // If we reach at the end of both strings, we are done
    if (*first == '\0' && *second == '\0')
        return true;
 
    // Make sure that the characters after '*' are present in second string.
    // This function assumes that the first string will not contain two
    // consecutive '*' 
    if (*first == '*' && *(first+1) != '\0' && *second == '\0')
        return false;
 
    // If the first string contains '?', or current characters of both 
    // strings match
    if (*first == '?' || *first == *second)
        return match(first+1, second+1);
 
    // If there is *, then there are two possibilities
    // a) We consider current character of second string
    // b) We ignore current character of second string.
    if (*first == '*')
        return match(first+1, second) || match(first, second+1);
    return false;

}

#include <iostream>
#include <vector>
#include <string.h>
#include <cstring>
#include <stack>
#include <algorithm>

/*input
txyBabABA
AA
*/


using namespace std;
vector<string> pa;

typedef struct t
{
    char data;
    struct t *left;
    struct t *right;
} tree;

tree* make_node(char data)
{
    tree *t = new tree;
    t->data = data;
    t->left = NULL;
    t->right = NULL;
    return t;
}
bool check_leaf(char c)
{
    if(c>=65&&c<97)
        return false;
    else if(c>=97&&c<122)
        return true;
}

tree* build_tree(string A,int *i)
{
    tree *t = make_node(A[*i]);
    if(i<0)
        return NULL;
	//if leaf then return the node no further building of tree.
    if(check_leaf(A[*i]))
        return t;
    *i = *i-1;
    //populate right subtree
    t->right = build_tree(A,i);
    *i = *i-1;
    //populate left subtree
    t->left = build_tree(A,i);
    return t;
}
void c_path(tree *t,char *path,int *i)
{
    if(t==NULL)
        return;
    if(check_leaf(t->data))
    {
        path[*i+1] = t->data;
        path[*i+2] = '\0';
        pa.push_back(path);
        return;
    }
    else{
        *i=*i+1;
        path[*i] = t->data;
        c_path(t->left,path,i);
        c_path(t->right,path,i);
        *i=*i-1;
        return;
    }
}

int sub_search(string a,string b)
{
    int i=0,j=0;
    while(i<a.size())
    {
        while(a[i]!=b[j]&&i<a.size())
            i++;
        if(i<a.size()&&j<b.size())
        {
            i++;
            j++;
        }
        else if(i>=a.size())
            return 0;
        if(j>=b.size())
            return 1;
    }
}






void print(tree *t)
{
    if(t==NULL)
        return;
    cout<<t->data<<" ";
    print(t->left);
    print(t->right);
}

int main()
{
    string post_order,po,a;
    cin>>post_order;
    cin>>a;
    int i= post_order.size()-1;
    tree *t = build_tree(post_order,&i);
    char *p= new char[10];
    i=-1;
    c_path(t,p,&i);
    int j = pa.size()-1;
    i=0;
    int cnt=0;

    while(j>=0){
        po = pa[j--];
        //cout<<po<<endl;
        cnt+=sub_search(po,a);
    }
    cout<<cnt;
    return 0;
}