Intelligent Substring | Interview Question | String | C++

 

Intelligent Substrings:

There are two types of characters in a particular language: special and normal. A character is special if its value is 1 and normal if its value is 0. Given string s, return the longest substring of s that contains at most k normal characters. Whether a character is normal is determined by a 26-digit bit string named charValue. Each digit in charValue corresponds to a lowercase letter in the English alphabet.

Example:

s = 'abcde'

alphabet = abcdefghijklmnopqrstuvwxyz

charValue = 10101111111111111111111111

For clarity, the alphabet is aligned with charValue below:

alphabet = abcdefghijklmnopqrstuvwxyz

charValue = 10101111111111111111111111

The only normal characters in the language (according to charValue) are b and d. The string s contains both of these characters. For k = 2, the longest substring of s that contains at most k = 2 normal characters is 5 characters long, abcde, so the return value is 5. If k = 1 instead, then the possible substrings are ['b', 'd', 'ab', 'bc', 'cd', 'de', 'abc', 'cde']. The longest substrings are 3 characters long, which would mean a return value of 3.

Solution In C++:

#include<iostream>

#include<string>

using namespace std;

int intelligentsubstring(string s,int k,string charvalue)

{

    int count=0;

    int start=0;

    int end=0;

    int n=s.size();

    int sol=0;

    while(end<n)

    {

        while(end<n && count<=k)

        {

            if(charvalue[s[end]-'a']=='0')

                count++;

            end++;    

        }

        sol=max(sol,end-start-1);

        while(start<=end && count>k)

        {

            if(charvalue[s[start]-'a']=='0')

                count--;

            start++;    

        }

    }

    return sol;

}

int main()

{

    string s;

    cin>>s;

    int k;

    cin>>k;

    string charvalue;

    cin>>charvalue;

    cout<<intelligentsubstring(s,k,charvalue)<<'\n';

    return 0;

}

Optimized and working solution.

Thank you.