DEV Community: pastaPicaso

Leetcode daily

pastaPicaso — Sat, 01 Mar 2025 07:24:47 +0000

Hi,

I wanted to you my idea for the solution for LC daily on date 28Feb2025.
The Problem is marked as hard, but its not actually very hard if you are familier with certain algorithm.

Problem description.

[[Shortest Common Substring]] find the shortest string that has given 2 strings as substring.

Example: str1 = "abac", str2 = "cab"
Solution: "cabac"

Initial Idea

on the surface this problem statement feels quite similer to "Least common substring problem", which requires us to find maximum length substring from given 2 strings. the solution for that requires DP (Dynamic Programming) approach. and we get the maximum common part that 2 strings have.
Maybe we can use the LCS's output in some way to find the common connecting part. and join that with remaining string to formulate a solution.

LCS implementation.

I used the standard DP implementation for LCS.

#include <iostream>
#include <vector>
using namespace std;

// Function to find and print the LCS
string longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Filling DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Backtracking to find the LCS string
    int i = m, j = n;
    string lcs;
    while (i > 0 && j > 0) {
        if (text1[i - 1] == text2[j - 1]) {  // If characters match, add to LCS
            lcs = text1[i - 1] + lcs;
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {  // Move in the direction of max value
            i--;
        } else {
            j--;
        }
    }

    return lcs;
}

Credits: chatgpt

So at the end we have the string "LCS". but we are not interesting in LCS. we want the "sieve" the LCS in between the 2 remaining strings, so that we can get the minimum possible string.

Illustration

Implementation

We want to save the common character's location in both strings.

   vector<int> ai , bi ;  
// Ai and Bi save the location of LCS in both A , and B resp.
        while(i > 0 &&  j > 0) {
            if ( a[i-1] == b[j-1]) {

                ai.push_back(i-1);
                bi.push_back(j-1);
                i--;j--;
            } else if (dp[i-1][j] > dp[i][j-1]) {
                i--;
            } else {
                j--;
            }
        }

reverse both Ai and Bi, to get the indices in increasing order.

 reverse(ai.begin(), ai.end());
 reverse(bi.begin(), bi.end());

Now in the resulting string we "combine" the information from LCS , string A , and string B. like this.

        ai.push_back(n); bi.push_back(m);
        for(int i = 0 ; i < ai.size();i++) {
            while(idx_a < ai[i]) 
                lcs += a[idx_a++];
            while(idx_b < bi[i]) 
                lcs += b[idx_b++];
            idx_a++;idx_b++;
            if (ai[i] != n)
            lcs += a[ai[i]];
        }

the idea can be boiled down to these steps. first add all A's characters , then B's characters, the add the Common character, and repeat.

Leetcode daily 2

pastaPicaso — Tue, 27 Aug 2024 16:48:07 +0000

Today's problem is standard problem of BFS,
But it can teach us some c++ concepts such as using priority_queue correctly.

For this specific solution i have made a custom element and overwritten the less-than operator for it.
this makes me go thru the graph in order of probablity.

higher probability region will be explored first.
and this solution is accepted.

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<int,double>>> adj(n);
        int cnt = 0;
        for(auto i : edges) {

            adj[i[0]].push_back({i[1], succProb[cnt]});
            adj[i[1]].push_back({i[0], succProb[cnt]});
            cnt++;
        } 
        struct  elem { 
            double prob;
            int point;
            bool operator < (const struct elem &a) const { 
                return this->prob < a.prob;
            }
        };
        /* will pick up higher probabilities first */

        vector<double> probs(n,0.);
        probs[start] = 1.;

        priority_queue<elem> pq;
        pq.push(elem{1., start});
        while(!pq.empty()) {
            elem t = pq.top();
            pq.pop();
            cout << t.point << endl; 
            if (t.point == end) { 
                break; 
            }
            for(auto i : adj[t.point])  { 
                // probs[i.first] = max(probs[i.first],
                //     probs[t.point] * i.second);
                // pq.push(elem{probs[i.first],i.first}); // we just push the point, and we dont care about the prob.
                if (probs[i.first] < probs[t.point] * i.second) { 
                    probs[i.first]  = probs[t.point] * i.second;
                    pq.push(elem{probs[i.first], i.first});
                }
            }
        }
        return probs[end];
    }
};

But seems like there are more complicated and FAST solutions for this problem.

For example using this Graph-DP.

which has half the runtime.

Leetcode daily

pastaPicaso — Mon, 19 Aug 2024 16:31:25 +0000

The problem statement was pretty simple,
Intially you a letter A written on the Notepad.
you can either of these 2 operations, however many times.

copy all the contents of the notepad (partial copy is not allowed)
paste the content from your copy at any location in the text.

I solved this problem using DP.
which looks very similer in implementation to sieve's algorithm to finding the prime.

here's my solution.

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n+3, INT_MAX);
        dp[1] = 0;
        for (int i = 2; i<= n;i++) {
            if (i % 2==0) { 
                dp[i] = min(dp[i], dp[i/2]+2);
            } else { 
                dp[i] = min(dp[i], i);
                for (int j = 2 * i ,times = 2; j <= n; j+=i, times++) { 
                    dp[j] = min(dp[j], dp[i] + times); 
                }
            }
        }
        return dp[n];
    }
};

Guide for operator overloading in C++

pastaPicaso — Sun, 18 Aug 2024 17:11:42 +0000

Hi,
Operator overloading is very powerful feature in C++.
just by itself, it might not sound very powerful, but combine it with programming API provide by C++ stdlib, ( STL, standard template library ) and you have a wonderful programming experience.

I'll listdown a program that solved using operator overloading.

Problem: https://leetcode.com/problems/ugly-number-ii/description/

Its a decent level problem on leetcode, and there are many solution ways. One of them is using priority_queue. Priority_queue is a template class in STL and it can be used in various standard ways.

Here's the defination of the template class, according to the cppreference.

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

the first one is the type of Queue, or the items that will be queue'd. The second is the Container which defaults to vector. and third one is the comparator operator.

Now thats cool and all but I like to use it in a different way. using custom struct.

Here's an example.

       struct A { 
            long long number; 
            bool operator <(const struct A a) const { 
                return this->number > a.number; 
            }
            struct A operator()(int a) { 
                this->number = a; 
                return *this; 
            }
            long long operator* (int a) { 
                return this->number * a; 
            }
        };
        priority_queue<A> pq;

For a struct to be a valid Queue-able item, it has to have a Comparator operator overloaded, i.e the less-than operator. The Priority_queue class will use this information will use this function to order the elements in the Container class.

Nows whats the other 2 overloads for?
they are to easily cast the Wrapper type to Integer or Numeral type. Based on the complete solution you can access that I have used the wrapper type directly with Arithematic operations, Thats possible because of the Operator overloading symantics.

C++ is just great.
Here's the complete solutions for the Leetcode problem.

    int nthUglyNumber(int n) {
        struct A { 
            long long number; 
            bool operator <(const struct A a) const { 
                return this->number > a.number; 
            }
            struct A operator()(int a) { 
                this->number = a; 
                return *this; 
            }
            long long operator* (int a) { 
                return this->number * a; 
            }
        };
        priority_queue<A> pq; 
        pq.push(A(1)); 
        int cnt = 1; 
        set<int> done; 
        done.insert(1);
        while(!pq.empty()) { 
            A k = pq.top(); 
            cout << k.number << endl; 
            if (cnt == n) { 
                return (int)k.number;
            }
            cnt++;
            pq.pop();
            if (!done.count(k*2))
                pq.push(A(k * 2)),done.insert(k*2); 
            if (!done.count(k*3))
                pq.push(A(k * 3)),done.insert(k*3); 
            if (!done.count(k*5))
                pq.push(A(k * 5)),done.insert(k*5); 

        }
        return 0;
    }

Codeforces Educational round 169 Div2 walkthru

pastaPicaso — Sun, 18 Aug 2024 15:50:19 +0000

Problem A:

there can be no solution if there are 3 or >3 different numbers, so we just have to think of == 2 case.
and also , if there isnt a number between the a[0] and a[1].

so solution can be written like this.

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

int main()  { 
    auto solve = [](void)->void { 
        int n; cin>>n; 
        vector<int> a(n); 
        for(auto &i : a ) cin>>i; 
        if ( n == 2 && (a[1] != a[0] + 1 )) { 
            cout << "YES\n"; 
        } else { 
            cout << "NO\n";
        }
    };
    int t; cin>>t; while(t--) solve();
    return 0 ; 
}

Problem B:

Here we are only concerned about the common length of 2 segments.
corner condition need to think of is that there end are same. so we have to acomodate for those numbers also.

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

int main() { 
    auto solve = [](void) -> void { 
        int l , r , L , R; 
        cin>>l>>r>>L>>R; 
        int commonL = max(l, L); 
        int commonR = min(r, R); 
        /* 
            ..l.......r|L.....R ...
        */
        int ans = commonR - commonL + 2;
        if ( ans < 2) { cout << 1 << endl; return; }
        if (r==R) ans--;
        if (l==L) ans--;
        cout << ans << endl; 
    };
    int t; cin>>t; while(t--)solve();
    return 0 ; 
}

Problem C:

Alice can never score less than B, because she has the first pick, and she will always pick the max. so we have to optimize the second to max's in the array. here's one way to do it.

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

int main() { 
    auto solve = [](void)->void { 
        int n,k; cin>>n>>k;
        vector<int> a(n); 
        for(auto &i : a )cin>>i; 
        sort(a.begin(), a.end());

        for(int i = n-2;i>=0;i-=2) { 
            if (k >= (a[i+1] - a[i])) { 
                k -= (a[i+1] - a[i]); 
                a[i] = a[i + 1];
            } else { 
                a[i] += k; 
                break; 
            }
        }
        long long A=0,B=0;
        for (int i = n-1, turn = 0 ; i>=0 ; i--,turn++) { 
            if (turn & 1 ) {
                B += a[i]; 
            } else A += a[i]; 

        }
        cout << A - B << endl; 
    };
    int t; cin>>t; while(t--) solve(); 
    return 0;
}

Problem D:

now this is a interesting problem. our main observation should be that if there is a common element between string L and string R , then we can find the path directly, but if not then we can find the path using the help of a intermediate number. like
for example
BR -> RY -> GY
so here intermediate in RY.
in my solution i used binary search to find the closest match to string RY next to string BR ( or rather position L ).
here's the implementation.

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

int main() { 
    auto solve = [](void )->void { 
        int n , m; 
        cin>>n>>m;
        map<pair<char,char>, vector<int>> M; 
        auto C = [](pair<char,char> a)->pair<char,char> {
            pair<char,char> b = a; 
            if( a.first > a.second) { 
                b = {a.second , a.first};
            }
            return b;
        };
        vector<string> input;
        for(int i = 0 ; i < n; i++) { 
            string t ; cin>>t; 
            input.push_back(t);
            M[C({t[0], t[1]})].push_back(i);
        }

        auto find = [&](vector<int> &a ,int pos)-> int { 
            if (a.size() == 0) return 1e9;
            // cout << "find : "; for(auto i : a )cout << i << " ";cout << endl; 
            const int n = a.size();
            int l = 0, r = n;
            while(l < r - 1 ){ 
                int mid = (l +r )/2; 
                if ( a[mid] <= pos ) {
                    l = mid; 
                } else { 
                    r = mid; 
                }
            }
            return l;
        };
        auto commonE = [](string a, string b) -> bool { 
            assert(a.size() == 2 ); 
            assert(b.size() == 2 );
            for (int i =0 ; i < 2; i++)
                for (int j = 0 ; j < 2; j++) 
                    if (a[i] == b[j]) 
                        return true; 
            return false; 
        };

        while(m--) {
            int L , R ; 
            cin>>L>>R; L--,R--;
            if ( commonE(input[L], input[R])) { 
                cout << abs( R - L )  << endl; 
            } else { 
                int ans = 1e9;
                for (int i = 0 ; i < 2; i++) { 
                    for (int j = 0 ; j < 2 ; j++){ 
                        char first = input[L][i];
                        char second = input[R][j]; 
                        // cout << ans << " " << first << " " << second << endl; 
                        int loc = find(M[C({first, second})], L);
                        if (loc == 1e9)
                            continue; 
                        int locM =  M[C({first,second})][loc];
                        ans = min(ans, abs(L - locM) + abs(locM - R)); 
                        // cout << "locM" << " " << locM << " loc " << loc << endl; 
                        if (loc != M[C({first,second})].size() -1 ){ 
                            int locM2 = M[C({first,second})][loc + 1]; 
                            ans = min(ans , abs(L - locM2) + abs(locM2 - R));
                        }
                    }
                }
                cout << (ans == 1e9 ? -1 : ans) << endl; 
            }
        }
    };
    int t; cin>>t; while(t--) solve();
    return 0 ;
}