LeetCode, GeeksForGeeks Problem of the day solution
Ir al canal en Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Mostrar más1 250
Suscriptores
+224 horas
+147 días
+2930 días
Archivo de publicaciones
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()
