algorithms

commit c86c8cdf1619b2e553effcc8de0d0af504772038
parent 5c2cacb54c304aa785e2455e4aecbc6342c2c9dd
Author: Andrew Laack <andrew@laack.co>
Date:   Fri, 28 Aug 2026 00:02:37 -0500

Another kahn's algorithm problem

Diffstat:
A
course-schedule-iv/course-schedule-iv.cpp
 | 
63
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
shortest-and-lexicographically-smallest-beautiful-string/shortest-and-lexicographically-smallest-beautiful-string.cpp
 | 
80
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 143 insertions(+), 0 deletions(-)
diff --git a/course-schedule-iv/course-schedule-iv.cpp b/course-schedule-iv/course-schedule-iv.cpp
@@ -0,0 +1,63 @@
+class Solution {
+public:
+    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
+        // must take numcourses
+        // 0 -> numCourses - 1
+        // prereq[i] = [a_i,b_i] must take a_i before b_i
+        // queries[j] = [u_j, v_j] you have to answer if u_j is a pre-req for v_j
+            // this can be a transitive pre-req too
+        // return answer where answer[j] answers queries[j]
+        // prereqs has no cycles
+
+        // idea:
+            // realize the entire dependency chain
+            // this would require a bunch of memory, but is possible
+                // O(n^2) specifically where n is the number of courses
+                    // course count is <= 100 though so at most there'd be ~10,000 edges
+        
+        // bool vectors are spooky so 1 == true, 0 == false
+        vector<vector<int>> isReachable{};
+
+
+        // how?
+            // do bfs from each node
+        
+        vector<vector<int>> dependencies(numCourses);
+
+        for(auto pre: prerequisites) {
+            dependencies[pre[0]].push_back(pre[1]);
+        }
+
+        for(int i = 0; i < numCourses; ++i) {
+            isReachable.push_back( bfs(numCourses, dependencies, i) );
+        }
+
+        vector<bool> answer{};
+        for(auto query: queries) {
+            answer.push_back(isReachable[query[0]][query[1]] == 1);
+        }
+
+        return answer;
+    }
+    private:
+        vector<int> bfs(int courses, vector<vector<int>>& dependencies, int current) {
+            vector<int> stack{};
+            vector<int> result(courses);
+
+            stack.push_back(current);
+
+            while(stack.size() > size_t{0}) {
+                int idx = stack.back();
+                stack.pop_back();
+                result[idx] = 1;
+                for(auto req: dependencies[idx]) {
+                    if(result[req] == 0) {
+                        stack.push_back(req);
+                    }
+                }
+            }
+
+            return result;
+        }
+
+};
diff --git a/shortest-and-lexicographically-smallest-beautiful-string/shortest-and-lexicographically-smallest-beautiful-string.cpp b/shortest-and-lexicographically-smallest-beautiful-string/shortest-and-lexicographically-smallest-beautiful-string.cpp
@@ -0,0 +1,80 @@
+class Solution {
+public:
+    string shortestBeautifulSubstring(string s, int k) {
+        // left = 0
+        // right = 0
+        // move right to right when num 1's < k
+        // once num 1's == k track this if the length 
+        // of this is < the shortest other string or if
+        // it is the same size set it as the best if it's a smaller number than the other matching one
+        // return once right == len(s)
+
+        int left = 0;
+        int right = 0;
+        int oneCount = 0;
+
+        if (s[0] == '1') {
+            oneCount += 1;
+        }
+
+        int bestLeft = -1;
+        int bestRight = -1;
+
+        while(right < s.size()) {
+            cout << oneCount << endl;
+            if(oneCount < k) {
+                right += 1;
+                if (right < s.size() && s[right] == '1'){
+                    oneCount += 1;
+                }
+                continue;
+            }
+            if(oneCount > k) {
+                left += 1;
+                if (left < s.size() && s[left - 1] == '1'){
+                    oneCount -= 1;
+                }
+                continue;
+            }
+            if(oneCount == k) {
+                if(right - left < bestRight - bestLeft || bestRight + bestLeft == -2 || (right - left == bestRight - bestLeft && larger(bestLeft, bestRight, left, right, s))) {
+                    bestLeft = left;
+                    bestRight = right;
+                }
+                if(left + 1 <= right) {
+                    left += 1;
+                    if (left < s.size() && s[left - 1] == '1'){
+                        oneCount -= 1;
+                    }
+                } else {
+                    right += 1;
+                    if (right < s.size() && s[right] == '1'){
+                        oneCount += 1;
+                    }
+                }
+
+                continue;
+            }
+        }
+
+        if(bestRight + bestLeft == -2) {
+            return "";
+        }
+        string best = s.substr(bestLeft, (bestRight - bestLeft) + 1);
+        return best;
+
+
+    }
+    private:
+        bool larger(int bestLeft, int bestRight, int left, int right, string& s) {
+            for(int i = 0; i < (bestRight - bestLeft) + 1; ++i) {
+                if(s[bestLeft + i] == '1' && s[left + i] == '0'){
+                    return true;
+                }
+                if(s[bestLeft + i] == '0' && s[left + i] == '1'){
+                    return false;
+                }
+            }
+            return true;
+        }
+};