LeetCode

In this post, we’ll be solving LeetCode problem 1143. We have two strings text1 and text2 with sizes \(n\) and \(m\), respectively. We want to find the length of their longest common subsequence (LCS). A subsequence of a string s is obtained by deleting zero or more characters from s. Strategy Let’s assume we have two strings: s1 with size n1 and s2 with size n2. Let’s also assume we know their LCS length. What can we say about LCS length when we append a character c1 to s1 and a character c2 to s2? ...

In this post, we’ll be solving LeetCode problem 2542. We have two integer arrays nums1 and nums2 with size \(n\), as well as an integer \(k\). Let’s denote nums1 with \(A\) and nums2 with \(B\). If we pick a set of indices \(S\) with exactly \(k\) elements, we obtain a score as follows: \[ \min \left\{ B_i | i \in S \right\} \sum_{i \in S} A_i \] There are many different sets \(S\) that give different scores. We want to find the maximum possible score. ...

In this post, we’ll be solving LeetCode problem 2236. We start with an infinite set containing all positive integers. We may remove and return the smallest integer using int popSmallest() or add a positive integer back into the set using void addBack(int num). Strategy If we only focus on popping smallest integers, then we only need to keep track of the smallest number in the set with a variable n. We start with n = 1. Each time we pop, we increment n by one. ...

A trie is data structure which holds strings. It allows fast search and insertion of strings, as well as fast search of string prefixes. This can be especially useful for text autocompletion and spellcheck. In this post, we implement a trie in C++ with three basic operations: search, insert, and startsWith. This is the solution to LeetCode 208. The problem assumes that all words use characters a-z in the English alphabet, but our solution can be extended to include more characters. ...