LeetCode, GeeksForGeeks Problem of the day solution

class Solution { public: bool ex(int ind, int op, string &s, vector>&dp){ if(ind == s.size()) return (op == 0); if(dp[ind][op] != -1) return dp[ind][op]; bool ans = false; if(s[ind] == '*'){ ans |= ex(ind+1, op+1, s, dp); if(op) ans |= ex(ind+1, op-1, s, dp); ans |= ex(ind+1, op, s, dp); }else{ if(s[ind]=='('){ ans = ex(ind+1, op+1, s, dp); }else{ if(op) ans = ex(ind+1, op-1,s ,dp); } } return dp[ind][op] = ans; } bool checkValidString(string s) { vector>dp(s.size(), vector(s.size(), -1)); return ex(0,0,s,dp); } };

class Solution{ public: int solve(int n, int m, int a[], int b[], vector> &dp) { if(m < 0) return 0; if(n < 0) return INT_MIN; if(dp[n][m] != -1) return dp[n][m]; int take = a[n] * b[m] + solve(n - 1, m - 1, a, b, dp); int not_take = solve(n - 1, m, a, b, dp); return dp[n][m] = max(take, not_take); } int maxDotProduct(int n, int m, int a[], int b[]) { vector> dp(n, vector(m, -1)); return solve(n - 1, m - 1, a, b, dp); } };

class Solution { public: string minRemoveToMakeValid(string s) { int n = s.length(); unordered_set<int> toRemove; stack<int> st; for(int i = 0; i<n; i++) { if(s[i] == '(') st.push(i); else if(s[i] == ')') { if(st.empty()) { toRemove.insert(i); } else { st.pop(); } } }while(!st.empty()) { toRemove.insert(st.top()); st.pop(); } string result = ""; for(int i = 0; i<n; i++) { if(toRemove.find(i) == toRemove.end()) result.push_back(s[i]); } return result; } };

class Solution { public: // Function to count number of ways to reach the nth stair // when order does not matter. long long countWays(int n) { return (long)n/2 +1; } };

class Solution { public: string makeGood(string s) { int i; stack<char> st; char x; string str=""; for(i=0;i<s.size();++i) { if(st.empty()) st.push(s[i]); else { x = st.top(); if(isupper(s[i])) { if(islower(x) && toupper(x)==s[i]) st.pop(); else st.push(s[i]); } if(islower(s[i])) { if(isupper(x) && tolower(x)==s[i]) st.pop(); else st.push(s[i]); } } } while(!st.empty()) { x = st.top(); str=str+x; st.pop(); } reverse(str.begin(),str.end()); return str; } };

class Solution { public: vectorarr; int n; vectordp; int rec(int i){ if(i==0)return 1; if(dp[i]!=-1)return dp[i]; dp[i]=1; for(int j=0;j=i-j)dp[i]=max(dp[i],1+rec(j)); } return dp[i]; } int min_operations(vector& nums) { // Code here arr=nums; n=arr.size(); dp.assign(n+1,-1); int maxi=-1e9; for(int i=0;i

class Solution { public: int maxDepth(string s) { stack st; int n=s.length(); int ans=0; for(int i=0;i

class Solution { public: //Function to find sum of all possible substrings of the given string. long long sumSubstrings(string s){ // long long int ans=0; long long int mod=1e9+7; long long int r=1,res=0; for(int i=s.size()-1;i>=0;i--){ // long long int res=(res+((s[i]-'0')*(i+1)*r)%mod)%mod; res%=mod; r=(r*10+1)%mod; r%=mod; } return(res); } };

class Solution { public: bool search(int i, int j, int row, int col, vector>& board, string &word, int k ){ if( k== word.size()){ return true; } if( i<0 or j<0 or i==row or j== col or board[i][j]!= word[k]){ return false; } char ch= board[i][j]; board[i][j]='-'; bool op1= search (i+1, j,row,col,board, word, k+1); bool op2= search (i, j+1,row,col,board, word, k+1); bool op3= search (i, j-1,row,col,board, word, k+1); bool op4= search (i-1, j,row,col,board, word, k+1); board[i][j]=ch; return op1 or op2 or op3 or op4 ; } bool exist(vector>& board, string word) { int row=board.size(); int col=board[0].size(); for(int i=0; i

class Solution { public: vector arr; bool visited = false; Node* LCA(Node* root, int x, int y) { if(!root)return NULL; if(root->data==x or root->data==y)return root; auto a=LCA(root->left,x,y),b=LCA(root->right,x,y); if(a and b)return root; if(a)return a; return b; } void rootToNode(Node* root, Node* node) { if(!root)return; if(!visited)arr.push_back(root->data); if(root==node)visited=true; rootToNode(root->left, node); rootToNode(root->right, node); if(!visited)arr.pop_back(); } int kthCommonAncestor(Node *root, int k,int x, int y) { auto node = LCA(root,x,y); rootToNode(root,node); if(arr.size()