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

void twiceIsEnough(string &s){
    int n=s.length();
    int i=0,j=0,ans=0;
    unordered_map<char,int>mp;
    while(i<n){
        while(j<i && mp[s[i]]==2){
            mp[s[j]]--;
            if(mp[s[j]]==0)mp.erase(s[j]);
            j++;
        }
        mp[s[i]]++;
        ans=max(ans,i-j+1);
        i++;
    }
    cout<<ans<<endl;
}

int main(){
    string s;
    cin>>s;
    twiceIsEnough(s);
}

Twice is enough ✅

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int dp[100001];
int solve(int n,vector<int>& ar,int ci){
    if(ci>=n) return INT_MAX;
    if(ci==n-1){
        return 0;
    }
    if(dp[ci]!=-1) return dp[ci];
    int a=INT_MAX,b=INT_MAX,c=INT_MAX;
    if(ci+1<n){
        int a1=0;
        a1+=abs(ar[ci]-ar[ci+1])+solve(n,ar,ci+1);
        a=min(a1,a);
    }
    if(ci+2<n){
        int b1=0;
        b1+=abs(ar[ci]-ar[ci+2])+solve(n,ar,ci+2);
        b=min(b1,b);
    }
    if(ci+3<n){
        int c1=0;
        c1+=abs(ar[ci]-ar[ci+3])+solve(n,ar,ci+3);
        c=min(c1,c);
    }
    return dp[ci]=min(a,min(b,c));
}
int main(){
    int n;
    cin>>n;
    vector<int>ar;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        ar.push_back(a);
    }
    if(n==1) return ar[0];
    memset(dp,-1,sizeof(dp));
    cout<<solve(n,ar,0);
}


3 jumps ✅

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

vector<pair<int, int>> solve(vector<pair<int, int>>& p, int K) {
    priority_queue<pair<int, pair<int, int>>> mh;
    for(auto& i : p) {
        int d = i.first * i.first + i.second * i.second;
        mh.push({d, i});
        if(mh.size() > K) {
            mh.pop();
        }
    }
    vector<pair<int, int>> res;
    while(!mh.empty()) {
        res.push_back(mh.top().second);
        mh.pop();
    }
    return res;
}

int main() {
    int N, K;
    cin >> N;
    vector<pair<int, int>> p(N);
    for(int i = 0; i < N; i++) {
        cin >> p[i].first >> p[i].second;
    }
    cin >> K;
    vector<pair<int, int>> np = solve(p, K);
    for(auto& i : np) {
        cout << i.first << " " << i.second << endl;
    }
    return 0;
}

At the center ✅

#include <iostream>
#include <vector>

using namespace std;

void solve(vector<int>& a, int n) {
    int ans = a[0];
    for (int i = 1; i < n; i++) {
        ans &= a[i];
    }
    cout << ans << " ";
}

int main() {

        int n;
        cin >> n;

        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }

        solve(v, n);

    return 0;
}

Minimum integer✅

Element on right ✅

longest common substring - Alpha set

Book shelf ✅

Company Name: SmartReach.io
Role: SDE 1
Batch eligible: 2023 and 2024 passouts

Apply: https://smartreach.freshteam.com/jobs/C8Ti_0q7_Qu4/software-development-engineer-1-sde-1-j6

def longest_beautiful_prefix(S, substrings):
    dp = {len(S): 0}

    for i in range(len(S) - 1, -1, -1):
        longest_prefix = 0

        for s in substrings:
            possible_end = i + len(s)

            if possible_end <= len(S) and S[i:possible_end] == s[::-1] and possible_end in dp:
                longest_prefix = max(longest_prefix, dp[possible_end] + len(s))

        dp[i] = longest_prefix

    return dp[0]

Longest Prefix ✅
Infosys

vector<string> CheckStringPairs(int t, vector<string> a, vector<string> b) {
    vector<string> ans;
    int n = a.size();

    for (int j = 0; j < n; j++) {
        unordered_map<char, int> ump1, ump2;

        if (a[j].size() != b[j].size()) {
            ans.push_back("NO");
            continue;
        }

        for (int i = 0; i < a[j].size(); i++) {
            ump1[a[j][i]]++;
        }

        for (int i = 0; i < b[j].size(); i++) {
            ump2[b[j][i]]++;
        }

        bool isPossible = true;

        for (auto c : ump1) {
            char cc = c.first;

            if (ump2.find(cc) == ump2.end() || ump2[cc] != ump1[cc]) {
                isPossible = false;
                break;
            }
        }

        if (isPossible) {
            ans.push_back("YES");
        } else {
            ans.push_back("NO");
        }
    }

    return ans;
}

Strange String ✅
Infosys

ll solve(ll n,ll m,vector<ll>a,vector<ll>b,vector<ll>t,vector<ll>&l,vector<ll>&r,vector<ll>&k)
{
    for(ll i=0;i<m;i++)
    {
        if(t[i]==1)
        {
            for(ll j=l[i]-1;j<r[i];j++)
              a[j]=a[j]+b[j]*k[i];
        }
        else{
            if(a[r[i]-l[i]]>k[i])
              a[r[i]-l[i]]=a[r[i]-l[i]]-((a[r[i]-l[i]]-k[i])+k[i]/2);
        }
    }
    ll sum=0;
    for(ll i=0;i<n;i++) sum=(sum%mod+a[i]%mod)%mod;
    return sum;
}

farmers fertiizers ✅
infosys

int beauty(vector<int>& a , int l , int r , int x){
     int res = 0;
    int cnt = 0;
    int i = l-1;
    while(i < r){
        if(a[i] == x){
         cnt++;
         res = max(cnt,res);
        }
        else if(a[i] > x){
            cnt = 0;
        }
        i++;
    }
    return res;
}
int GetAns(int n , vector<int> a, int q , int three , vector<vector<int>> queries){
   
   long long sum = 0;
   int Mod = 1e9 + 7;
   for(int i = 0 ;i < q ;i++){
       sum += beauty(a,queries[i][0] , queries[i][1] ,queries[i][2]);
       sum %= Mod;
   }
   return sum;
}

Max queries
Infosys ✅

Grid partial ✅
Infosys

int largerPath(int node,vector<int>adjLis[],vector<int>&a,vector<int>&more){
  if(more[node]!=-1) return more[node];
  int ans=0;
  for(auto& it:adjLis[node]){
    if(a[it-1]<=a[node-1]) continue;
    ans=max(ans,largerPath(it,adjLis,a,more));
  }
  return more[node]=1+ans;
}
int smallerPath(int node,vector<int>adjLis[],vector<int>&a,vector<int>&less){
  if(less[node]!=-1) return less[node];
  int ans=0;
  for(auto& it:adjLis[node]){
    if(a[it-1]>=a[node-1]) continue;
    ans=max(ans,smallerPath(it,adjLis,a,less));
  }
  return less[node]=1+ans;
}
vector<int>frog(int n,int m,int c,vector<int>a,vector<vector<int>>edges){
    vector<int>adjLis[n+1];
    for(auto& it:edges){
        adjLis[it[0]].push_back(it[1]);
        adjLis[it[1]].push_back(it[0]);
    }
    vector<int>less(n+1,-1),more(n+1,-1);
    vector<int>ans;
    for(int i=1;i<=n;i++){
        int tot=smallerPath(i,adjLis,a,less)+largerPath(i,adjLis,a,more)-1;
       ans.push_back(tot);
    }
    return ans;
}

Frog ✅
Infosys

#include <iostream>
#include <vector>

using namespace std;

int solver(int idx, vector<int>& A) {
    if (idx >= A.size()) return 0;
    int pick = A[idx] + solver(idx + 2, A);
    int notpick = solver(idx + 1, A);
    return max(pick, notpick);
}

int solve(int n, vector<int>& A, int q, vector<vector<int>>& queries) {
    int ans = 0;
    for (auto it : queries) {
        int index = it[0];
        int value = it[1];
        A[index] -= value;
        ans += solver(0, A);
    }
    return ans;
}

int main() {
    int n;
    cin >> n;

    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    int q;
    cin >> q;

    vector<vector<int>> queries(q, vector<int>(2));
    for (int i = 0; i < q; ++i) {
        cin >> queries[i][0] >> queries[i][1];
    }

    int result = solve(n, A, q, queries);
    cout << result << endl;

    return 0;
}



yet another subsequence ✅
Infosys

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[10005][2];
const int mod = (1e9 + 7);

ll solve(ll i, ll o, ll n, ll k, vector<ll> &v) {
    if (i > n) {
        return 0;
    }
    if (dp[i][o] != -1)
        return dp[i][o];
    ll ans = 0;
    if (o == 0) {
        for (int j = i; j < min(n + 1, i + k); j++) {
            ans = max(ans, solve(j + 1, 1 - o, n, k, v)) % mod;
        }
    } else {
        ll ta = 0;
        ll mx = 0;
        for (int j = i; j < min(n + 1, i + k); j++) {
            if (ta + v[j] >= 0) {
                ta += v[j];
                mx = max(mx, ta);
            } else {
                ta = 0;
            }
            ll c = solve(j + 1, 1 - o, n, k, v) % mod;
            ans = max(ans, ((j - i + 1) * mx) % mod + c % mod);
        }
    }
    return dp[i][o] = ans;
}

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> v;
    ll neg = 0;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        v.push_back(x);
        if (x <= 0)
            neg++;
    }

    if (neg == v.size()) {
        cout << 0 << endl;
        return 1;
    }
    memset(dp, -1, sizeof(dp));
 
    cout << max(solve(0, 0, v.size() - 1, k, v), solve(0, 1, v.size() - 1, k, v)) << endl;
}

Array Segment
Infosys ✅

#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>

using namespace std;

int smartTaxiDriver(int N, int K, vector<int>& T, vector<int>& P, vector<int>& C) {
    unordered_map<int, vector<pair<int, int>>> g;

    for (int i = 0; i < N - 1; ++i) {
        g[P[i] - 1].push_back({i + 2, C[i]});
    }

    int mpc = 0;

    for (int sn = 1; sn <= N; ++sn) {
        vector<int> d(N + 1, -1);
        d[sn] = 0;
        deque<pair<int, int>> q = {{sn, 0}};

        while (!q.empty()) {
            auto [cn, cd] = q.front();
            q.pop_front();

            for (auto& [ne, rd] : g[cn]) {
                if (d[ne] == -1 || d[ne] > cd + rd) {
                    d[ne] = cd + rd;
                    q.push_back({ne, d[ne]});
                }
            }
        }

        int pc = 0;
        for (int des : T) {
            if (d[des] <= K) {
                pc++;
            }
        }

        mpc = max(mpc, pc);
    }

    return mpc - 1;
}

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> T(N - 1), P(N - 1), C(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        cin >> T[i];
    }
    for (int i = 0; i < N - 1; ++i) {
        cin >> P[i];
    }
    for (int i = 0; i < N - 1; ++i) {
        cin >> C[i];
    }

    int res = smartTaxiDriver(N, K, T, P, C);
    cout << res << endl;

    return 0;
}

Smart Taxi Driver ✅
Infosys

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

void solve(vector<vector<int>> vv, int operation, int xx, int yy, int &res)
{

    for (int i = 1; i < 3; i++)
    {
        int sum1 = 0;
        for (int j = 0; j < vv.size(); j++)
        {
            sum1 += vv[j][i - 1];
        }
        int sum2 = 0;
        for (int j = 0; j < vv.size(); j++)
        {
            sum2 += vv[j][i];
        }
        if (sum1 == sum2)
        {
            res = min(res, operation);
        }

        return;
    }
    for (int i = 0; i < vv.size(); i++)
    {
        solve(vv, operation, xx, yy, res);
        vector<int> p1 = vv[i];
        reverse(p1.begin(), p1.end());
        solve(vv, operation + yy, xx, yy, res);
        vector<int> p2 = vv[i];
        int temp1 = p2[0];
        int temp2 = p2[1];
        int temp3 = p2[2];
        p2[2] = temp1;
        p2[1] = temp3;
        p2[0] = temp2;
        solve(vv, operation + xx, xx, yy, res);
        vector<int> p3 = vv[i];
        temp1 = p2[0];
        temp2 = p2[1];
        temp3 = p2[2];
        p2[2] = temp2;
        p2[1] = temp1;
        p2[0] = temp3;
        solve(vv, operation + xx, xx, yy, res);
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;

    while (t--)
    {
        int n = 0, m = 0, a = 0, b = 0, c = 0, d = 0, sum = 0, diff = 0, maxN = 0, minN = 0, count = 0, temp = 0;
        bool flag = false;
        cin >> n;

        cin >> m;
        int xx;
        cin >> xx;
        int yy;
        cin >> yy;
        vector<vector<int>> vv(n, vector<int>(m));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> vv[i][j];
            }
        }
        if (n == 1)
        {
            cout << -1 << endl;
            continue;
        }
        int res = INT_MAX;
        solve(vv, 0, xx, yy, res);
        cout << res << endl;
    }
    return 0;
}

Pay for Gift ✅
Infosys

#include <iostream>
#include <vector>

const int MOD = 1000000007;

using namespace std;

int countBeautifulSequences(int n) {
    if (n == 1) {
        return 1;
    }

    vector<int> dp(n + 1, 0);
    dp[1] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            dp[j] = (dp[j] + dp[j - i]) % MOD;
        }
    }

    return (dp[n] - 1 + MOD) % MOD;
}

int main() {
    int n;
    cin >> n;

    int result = countBeautifulSequences(n);
    cout << result << endl;

    return 0;
}

Count Beautiful sequence

ll help(ll ans,ll k,map<pair<ll,ll>,ll>&m){
    //cout<<ans<<endl;
    if(k==0)
      return ans;
     if(m.find({ans,k})!=m.end())
       return m[{ans,k}];
     ll a=ans;
    for(ll i=30;i>=0;i--){
        for(ll j=30;j>=0;j--){
            ll k1=(ans|(1LL<<i))^(1LL<<j);
            //cout<<k1<<endl;
            a=max(a,help(k1,k-1,m));
        }
    }
    m[{ans,k}]=a;
    return a;
}
void solve(vector<ll>a,ll k){
    ll n=a.size();
    ll ans=a[0];
    for(ll i=1;i<n;i++){
        ans &=a[i];
    }
    map<pair<ll,ll>,ll>m;
    cout<<help(ans,k,m);
}

Limited mask

int min_operations(string s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < n; i++) {
        dp[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
            } else {
                for (int k = i; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + 1);
                }
            }
        }
    }

    return dp[0][n - 1];
}

String Dot
Infosys