HackerEarth Fashion Line problem solution

YASH PAL,
In this HackerEarth Fashion Line problem solution, Rachel works at a big fashion organization. There is a big event coming up and she has to select dresses for an exhibition.
She has N dresses numbered 1 to N. There is a total of 62 types of dresses, each represented by a different alphanumeric character (a-z, A-Z, 0-9). The N dresses are represented by a string S of length N of alphanumeric characters. The ith character of S denotes the type of the ith dress. Rachel will select two integers, A and B such that 1 <= A <= B <= N and take the dresses numbered from A to B to the exhibition.
Out of the 62 dress types, K dress types are special. Find the number of values of A and B possible such that the total number of special dresses of any type selected is at least L and at most R.
HackerEarth Fashion Line problem solution

HackerEarth Fashion Line problem solution.

#include<bits/stdc++.h>
using namespace std;
int getCharId(char ch)
{
    if(ch>='a' && ch<='z')
        return ch-'a';
    else if(ch>='A' && ch<='Z')
        return ch-'A'+26;
    else if(ch>='0' && ch<='9')
        return ch-'0'+52;
    else
        return -1;
}
int main()
{
    int T;
    cin>>T;
    assert(1<=T && T<=100);
    while(T--)
    {
        char str[10001],special[10001];
        int N,mark[62]={0},K,i,L,R;
        cin>>N>>K>>L>>R;
        assert(1<=N  && N<=10000 && 1<=K && K<=62 && 0<=L && L<=N && 0<=R && R<=N && L<=R);
        cin>>str>>special;
        assert(strlen(str)==N);
        assert(strlen(special)==K);
        for(i=0;i<K;i++)
        {          
            mark[getCharId(special[i])]=1;
        }
        int next[100001],next_c=0;
        int len=strlen(str);
        for(i=0;i<len;i++)
        {
            if(mark[getCharId(str[i])]==1)
            {
                next[next_c]=i;
                next_c++;
            }
        }
        long long ans=0,next_i=0;
        for(i=0;i<len;i++)
        {
            
            if(next_i+L-1>=next_c)
                break;
                
            int till1=i;
            if(L!=0)
                till1=next[next_i+L-1];
            int till2=len-1;
            if(next_i+R<next_c)
            {
                till2=next[next_i+R]-1;
            }
            
            if(till1<=till2)
            {
                ans+=(till2-till1+1);
            }
            if(mark[getCharId(str[i])]==1)
                next_i++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

bool chk[252];
int dp[10002];

int main()
{
  int t,n,m,l,r;
  string s,p;

  int ans;

  cin >> t;
  assert(t>=1&&t<=100);
  while ( t-- ) {
    memset(chk, false, sizeof(chk));
    cin >> n >> m >> l >> r;
    assert(n>=1&&n<=10000);
    assert(m>=1&&m<=62);
    cin >> s >> p;
    assert(s.size() == n);
    assert(p.size() == m);
    assert(l>=0&&l<=n);
    assert(r>=0&&r<=n);
    assert(l<=r);
    for ( int i = 0; i < p.size(); i++ ) {
      assert(p[i]>=0&&p[i]<=251);
      chk[p[i]] = true;
    }
    dp[0] = 0;
    ans = 0;
    for ( int i = 1; i <= n; i++ ) {
      assert(s[i-1]>=0&&s[i-1]<=251);
      dp[i] = dp[i-1] + chk[s[i-1]];
    }
    for ( int i = 1; i <= n; i++ ) {
      int lf,rt,md,fs=-1,sc=n+1;
      lf = i, rt = n, md = -1;
      while ( lf <= rt ) {
        md = (lf+rt)/2;
        int val = dp[md] - dp[i-1];
        if ( val >= l ) {
          fs = md;
          rt = md-1;
        }
        else if ( val < l ) lf = md+1;
      }
      if ( fs == -1 ) continue;
      lf = i,rt = n, md = -1;
      while ( lf <= rt ) {
        md = (lf+rt)/2;
        int val = dp[md] - dp[i-1];
        if ( val > r ) {
          sc = md;
          rt = md-1;
        }
        else lf = md+1;
      }
      ans += sc-fs;
    }
    cout << ans << endl;
  }
  return 0;
}
coding problems