165C. Another Problem on Strings - Codeforces Solution C++ ~ CodingWithArt

➤ Problem Link : 165C. Another Problem on Strings

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
int main()
{
  int k;
  string s;
  cin>>k;
  cin>>s;
  ll cum[s.length()+1];
  unordered_map<ll,pair<ll,ll> > mp;
  for(int i=0;i<s.length();i++)
  {
    if(i==0)
      cum[i]=s[i]-'0';
    else
      cum[i]=s[i]-'0'+cum[i-1];
 
    if(mp.find(cum[i])==mp.end())
      mp[cum[i]]=make_pair(i,i);
    else
      mp[cum[i]].second=i;
  }
  ll prev=0,fin,l,r,ans=0;
  for(int i=0;i<s.length();i++)
  {
    if(i!=0)
      prev=cum[i-1];
    fin = prev + k ;
    if(mp.find(fin)==mp.end())
        continue;
    l = max(mp[fin].first,(ll)i);
    r = mp[fin].second;
 
    if(l<=r)
      ans+=r-l+1;
      
 
 
  }
  cout<<ans;
 
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.