GeeksForGeeks - POTD | GFG POTD Answer

class Solution{ 
 public: 
  vector<string> AllPossibleStrings(string s){  
      vector<string> result; 
      int n=s.length(); 
      for(int i=1;i <= (1<<n);i++) 
      { 
          string c; 
          for(int j=0;j<n;j++) 
          { 
              if((i & (1<<j))>0) 
                  c.push_back(s[j]); 
          } 
          if(c.length()>0) 
              result.push_back(c); 
      } 
      sort(result.begin(),result.end()); 
      return result; 
       
  } 
};

class Solution 
{ 
    public: 
    long long int count(long long int n) 
    { 
      vector<int>dp(n+1,0); 
        dp[0] = 1; 
         
        for(int i=3;i<=n;i++){ 
            dp[i] +=dp[i-3]; 
        } 
        for(int i=5;i<=n;i++){ 
            dp[i] +=dp[i-5]; 
        } 
        for(int i=10;i<=n;i++){ 
            dp[i] +=dp[i-10]; 
        } 
        return dp[n]; 
      
    } 
};

class Solution { 
public: 
    int maxSum(int n) { 
        vector<int> dp(n + 1); 
         
        // Base cases 
        dp[0] = 0; 
         
        for (int i = 1; i <= n; ++i) { 
            dp[i] = max(i, dp[i/2] + dp[i/3] + dp[i/4]); 
        } 
         
        return dp[n]; 
    } 
};

class Solution 
{ 
    public:  
         
        int maxProfit(vector<int>&price){  
      int n = price.size(); 
            vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (2, vector<int> (3, 0))); 
 
            for(int i = n - 1; i > -1; i--) { 
                for(int j = 0; j < 2; j++){ 
                    for(int k = 1; k < 3; k++) { 
                        dp[i][j][k] = 0; 
 
                        if(j) { 
                            dp[i][j][k] = max(price[i] + dp[i + 1][0][k - 1], dp[i + 1][1][k]);        
                        } 
                        else { 
                            dp[i][j][k] = max(-price[i] + dp[i + 1][1][k], dp[i + 1][0][k]); 
                        } 
                    } 
                } 
            } 
 
            return dp[0][0][2];  } 
};

class Solution 
{ 
    public: 
    int subsequenceCount(string s, string t) 
    { 
      int n1=s.size(),n2 = t.size(),dp[n1+1][n2+1],mod = 1e9+7; 
        memset(dp,0,sizeof(dp)); 
        for(int i=0;i<=n1;i++){ 
            dp[i][0] = 1; 
        } 
        for(int i=1;i<=n1;i++){ 
            for(int j=1;j<=n2;j++){ 
                dp[i][j] = dp[i-1][j]; 
                if(s[i-1]==t[j-1]) 
                    dp[i][j] = (dp[i][j] + dp[i-1][j-1])%mod; 
            } 
        } 
        return dp[n1][n2]; 
    } 
};

class Solution{ 
public: 
     
    int solve(int n,string &s,int i,int j,bool need,vector<vector<vector<int>>>&dp){ 
        // the parenthesis at i means just in the lhs of the the ith index 
        if(i+1==j){ 
            if(need==false){ 
                return (s[i]=='F')?1:0; 
            } 
            else{ 
                return (s[i]=='F')?0:1; 
            } 
        } 
        if(i>j){ 
            return 0; 
        } 
         
        if(dp[i][j][need]!=-1){ 
            return dp[i][j][need]; 
        } 
        int ans = 0; 
        for(int k = i+1;k<j;k+=2){ 
            if(s[k]=='^'){ 
                if(need==true){ 
                    int ct1 = solve(n,s,i,k,true,dp);//1 
                    int ct2 = solve(n,s,k+1,j,false,dp);//1 
                    int ct3 = solve(n,s,i,k,false,dp);//0 
                    int ct4 = solve(n,s,k+1,j,true,dp);//0 
                    ans = ans + ct1*ct2 + ct3*ct4; 
                } 
                else{ 
                    int ct1 = solve(n,s,i,k,true,dp); 
                    int ct2 = solve(n,s,k+1,j,true,dp); 
                    int ct3 = solve(n,s,i,k,false,dp); 
                    int ct4 = solve(n,s,k+1,j,false,dp); 
                    ans = ans + ct1*ct2 + ct3*ct4; 
                } 
            } 
            else if(s[k]=='|'){ 
                if(need==true){ 
                    int ct1 = solve(n,s,i,k,true,dp); 
                    int ct2 = solve(n,s,k+1,j,false,dp); 
                    int ct3 = solve(n,s,k+1,j,true,dp); 
                     
                    int ct4 = solve(n,s,i,k,false,dp); 
                    int ct5 = solve(n,s,i,k,true,dp); 
                    int ct6 = solve(n,s,k+1,j,true,dp); 
                    ans = ans + ct1*ct2+ct1*ct3+ct6*ct4; 
                } 
                else{ 
                    int ct1 = solve(n,s,i,k,false,dp);//1 
                    int ct2 = solve(n,s,k+1,j,false,dp);//1 
                    ans = ans + ct1*ct2; 
                } 
            } 
            else{ 
                if(need == true){ 
                    int ct1 = solve(n,s,i,k,true,dp); 
                    int ct2 = solve(n,s,k+1,j,true,dp); 
                    ans = ans + ct1*ct2; 
                } 
                else{ 
                    int ct1 = solve(n,s,i,k,true,dp); 
                    int ct2 = solve(n,s,k+1,j,false,dp); 
                     
                    int ct4 = solve(n,s,i,k,false,dp); 
                    int ct5 = solve(n,s,k+1,j,true,dp); 
                    ans = ans + ct1*ct2 + ct4*ct5 + ct4*ct2; 
                } 
            } 
        } 
        return dp[i][j][need] = (ans%1003); 
    } 
    int countWays(int n, string s){ 
        vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(n+1,vector<int>(2,-1))); 
        return solve(n,s,0,s.size(),true,dp); 
    } 
};

class Solution 
{ 
public: 
    set<string> st; 
     
    bool solve(int i, int n, string &s) 
    { 
        if(i==n) return true; 
        string temp = ""; 
        bool ans = false; 
        for(int j = i; j < n; j++) 
        { 
            temp+=s[j]; 
            if(st.find(temp)!=st.end()) 
            { 
                ans = ans|| solve(j+1, n, s); 
            } 
        } 
         
        return ans; 
    } 
    int wordBreak(string A, vector<string> &B) { 
        int n = A.size(); 
        int m = B.size(); 
        for(int i = 0; i < m; i++) st.insert(B[i]); 
        return solve(0, n, A); 
    } 
};

class Solution{ 
public: 
    int minValue(string s, int k){ 
        
        vector<int> f(26, 0); 
        for(auto i : s) 
            ++f[i - 'a']; 
 
        priority_queue<int> pq; 
        for(auto i : f) 
            if(i) 
                pq.push(i); 
 
        while(k-- and pq.size()){ 
            int x = pq.top(); 
            pq.pop(); 
            --x; 
 
            if(x) 
                pq.push(x); 
        } 
 
        int ans = 0; 
 
        while(pq.size()){ 
            ans += pq.top() * pq.top(); 
            pq.pop(); 
        } 
 
        return ans; 
    } 
};