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; 
}

/* 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; 
}

/* 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; 
}

#include <bits/stdc++.h>
using namespace std;
// #define   int  long long 
// void c_p_c()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifndef ONLINE_JUDGE
//     freopen("inputmst.txt", "r", stdin);
//     freopen("outputmst.txt", "w", stdout);
// #endif
// }
int main()
{
	// c_p_c();
    string s,num;
    cin>>s>>num;
    int k;
    cin>>k;
    vector<int> v(26,0);
    int m=0;
    for(char ch:num)
    {
         int val=ch-'0';
         v[m]=val;
         m++;
    }
    vector<int> nums(s.length(),0);
    m=0;
    for(char ch:s)
    {
        nums[m]=v[ch-'a'];
        m++;
    }
    int ans=0;
    int count=0;
    int st=0;
    for(int i=0;i<s.length();i++)
    {
        count+=nums[i];
        while(i-st+1-count>k)
        {
             count-=nums[st++];
        }
        ans=max(ans,i-st+1);
    }
    cout<<ans<<endl;
}

#include<bits/stdc++.h>
using namespace std;

int solve(string str, unordered_map<char, int> umap, int k){
	int count = 0, maxSize = 0;
	int i = 0, j = 0;
	while(j < str.length()){
		if(umap[str[j]] == 1){
			count++;
		}
		while(count > k and i <= j){
			if(umap[str[i]] == 1){
				count--;
			}
			i++;
		}
		maxSize = max(maxSize, j - i + 1);
		j++;
	}
	return maxSize;
}

int main(){
	string p, q;
	cin>>p;
	cin>>q;
	int k;
	cin>>k;
	unordered_map<char, int> umap;
	for(int i = 0; i < 26; i++){
		if(q[i] == '0'){
			umap[i + 'a']++;
		}
	}
	cout<<solve(p, umap, k)<<endl;
}

O(n) solution using sliding window technique...

s = input()
chVal = input()
l = []
k = int(input())
for i in s:
    l.append(chVal[ord(i)-ord('a')])
i = 0
for j in range(len(l)):
    if (l[j] == '0'): k -= 1
    if (k < 0):
        if l[i] == '0':
            k += 1
        i += 1
print(j+1-i)

O(n) solution using sliding window....

s = input()
chVal = input()
l = []
k = int(input())
for i in s:
    l.append(chVal[ord(i)-ord('a')])
i = 0
for j in range(len(l)):
    if (l[j] == '0'): k -= 1
    if (k < 0):
        if l[i] == '0':
            k += 1
        i += 1
print(j+1-i)