Posts

The power of pruning in backtracking VI

-
Image
Backtracking is a powerful strategy, and yes if can become exponential even with pruning, but remember that exponential might still be acceptable depending on the size of the input. For instance, in this case there isn't a lot of pruning and the solution ends up being N^4, but N = 15 in this case which is about 50K iterations which is for all practical purposes a "linear" solution. Code is down below, cheers, ACC. Word Squares II - LeetCode You are given a string array  words , consisting of  distinct  4-letter strings, each containing lowercase English letters. A  word square  consists of 4  distinct  words:  top ,  left ,  right  and  bottom , arranged as follows: top  forms the  top row . bottom  forms the  bottom row . left  forms the  left column  (top to bottom). right  forms the  right column  (top to bottom). It must satisfy: top[0] == left[0] ,  top[3] == right[0] ...
Post a Comment
Read more

Happy New Year - Frequency Count

-
Image
Happy 2026. First problem is a medium difficulty, just use frequency count (hint is that we're dealing only with lowercase letters). Also make sure to use long to avoid overflow. Code is down below, cheers, ACC. Minimum Deletion Cost to Make All Characters Equal - LeetCode You are given a string  s  of length  n  and an integer array  cost  of the same length, where  cost[i]  is the cost to  delete  the  i th  character of  s . You may delete any number of characters from  s  (possibly none), such that the resulting string is  non-empty  and consists of  equal  characters. Return an integer denoting the  minimum  total deletion cost required.   Example 1: Input:   s = "aabaac", cost = [1,2,3,4,1,10] Output:   11 Explanation: Deleting the characters at indices 0, 1, 2, 3, 4 results in the string  "c" , which consists of equal characters, and the total cost is ...
Post a Comment
Read more