Problems
December 4, 2022
Minimum average difference
We will use prefix sum to solve this problem. We will calculate the prefix sum of the first half of the array and the second half of the array. Then we will iterate over the first half of the array...
ReadDecember 4, 2022
Minimum number of steps to make two strings anagram II
We will count the character frequency of both the strings. We will iterate over the character frequency of the first string and for each character we will find the number of characters that we need...
ReadDecember 4, 2022
Implement trie II (prefix tree)
We will use a trie to solve this problem. We will store the count of each word in the trie. We will also store the count of each prefix in the trie. We will increment the count of the word and the...
ReadDecember 4, 2022
Minimum number of steps to make two strings anagram
We will count the character frequency of both the strings. We will iterate over the character frequency of the first string and for each character we will find the number of characters that we need...
ReadDecember 3, 2022
Longest substring with at most k distinct characters
We will use a sliding window to solve this problem. The window will be a substring of the input string. The window will be valid if it has at most k distinct characters. We will keep track of the...
ReadDecember 3, 2022
Longest string chain
We will use DFS to find the lognest possible word chain end at word. To calculate dfs(word), we try all predecessors of word word and get the maximum length among them. Time complexity:...
ReadDecember 3, 2022
Find k length substrings with no repeated characters
We will use a sliding window to solve this problem. The window will be a substring of the input string. The window will be valid if it has no repeated characters. We will keep track of the number of...
ReadJuly 25, 2022
Number of connected components in an undirected graph
First we will create an adjacency list from the edges. Then we will run DFS from the very first node, and added it to out visited set, also count it as a connected component. In the process of DFS...
ReadDecember 3, 2022
Longest substring with at most two distinct characters
We will use a sliding window to solve this problem. The window will be a substring of the input string. The window will be valid if it has at most two distinct characters. We will keep track of the...
ReadDecember 3, 2022
Number of subarrays with gcd equal to k
We will take every possible subarray of the input array and calculate the gcd of the subarray. If the gcd is equal to k, we will increment the count of such subarrays. Time complexity:...
Read