https://neetcode.io/problems/anagram-groups/question?list=neetcode150

Metric: Output is a list of lists where each sublist contains strings in different orders but same contents

Constraints: Each sublist has the same frequency of characters

Simplify: If we just had to add strings of the same characters how would we do it? (eg number doesn’t matter) (Idk if this is the right simplification)

For each string we basically have a seen list We could create a dictionary where the key is the seen list and the value is a list of all strings that have all those letters

So we could iterate through the strings: So the key is that we need to be able to compare these even out of order. You could build a key where we are guaranteed to have O(charset) where we just flip each char if seen And then to create the key for every true value we add it to our key

so for bca -> abc

So for group anagrams we can do something similar where instead of a boolean we just use the number

So we have

abc -> a1b1c1

bbaacc -> a2b2c2

So our pseudocode becomes:

1. For each string
   1. Create the key string O(charset)
   2. Add the current string to anagrams[key_string].append(string) Once we’ve done that we can then loop through the dict and just add each list to the result

https://neetcode.io/problems/top-k-elements-in-list/question?list=neetcode150

Metric: Top k most frequent elements -> Order by most frequent to least frequent and then return the first k elements

Constraints:

• Numbers are not sorted by frequency
• Top k elements need to be returned Ok I’m not sure if these are the right metrics and constraints but I’m going to try with them anyways feel free to tell me if there are better metrics and constraints here

Simplify:

• If I just had to return the most frequent element what would I do?
• Iterate through the list
  • Keep track of each element’s frequency
  • Keep track of a most frequent element
• Return this most frequent element

Now we need to layer in the constraint

• We need the top k elements so we have to keep track of multiple and not just the most frequent

• How do we keep track of multiple?

  • So frequencies should be sorted
  • How can we sort these frequencies?
  • If we break this down by a per element phase
  • Each time we see an element in the list
    • If it hasn’t been seen before we add its count as 1 and we can add it to the end of the frequency list
    • If we have seen it before
      • We increment its frequency and push it above all frequencies that are lesser
      • In a sense because we only ever add 1 at a time we are just pushing it to the next level essentially
      • So what operation can we use here to easily add and remove an item from a group?
        • I think set becomes the most applicable but we’ll need a set per frequency
        • So then my thought becomes that we should have a frequency = numbers dict?
        • when we see a number if we’ve never seen it before we would need to add it to freq 0
        • But if we have seen it before we would need to see where it currently is and then increment that

• So essentially we have two data structures it seems

  • Number -> frequency
  • Frequency -> numbers in this frequency
  • And we just update these as we see them
  • Both are O(1) updates since we have O(1) access to hashset and adding and removing from a set should also be around O(1)

• Pseudocode:

• number_to_freq =

• freq_to_number =

• For item in array:

  • If not in number_to_freq:
    • number_to_freq[number] = 1
    • freq_to_number[1].add(number)
  • If in number_to_freq:
    • old = number_to_freq[number]
    • freq_to_number[old].remove(number)
    • new = old + 1
    • number_to_freq[number] = new
    • freq_to_number[new].add(number)

• sorted_keys = sorted(freq_to_number.keys(), reverse=True)

• top_k = []

• k-remaining = k

• for x in sorted_keys:

  • if k-remaining >= len(freq_to_number[x]):
    • top_k += freq_to_number[x]
    • k-remaining = k - len(top_k)
  • else:
    • top_k += freq_to_number[x][:k-remaining]
    • return top_k

• return top_k

https://neetcode.io/problems/permutation-string/question?list=neetcode150

Metric:

• Does s2 contain a permutation (Frequency equal to or greater per character) of s1
• substring so it needs to be in order Constraints:
• Substring, so it needs to be same length
• Within window, same frequency Simpler version:
• Substring

1. We would go ahead and place pointers on l = 0 and r = len(s1)
2. Then we would iterate through s2 keeping this window and seeing if it would match Layer back in the constraint

• we can keep track of the frequency of each letter in the window
• So on each iteration we
  • Check if current string matches
  • If it doesn’t
    • move R
      • Add to frequency
    • move L
      • remove from frequency

So then we basically iterate through this s2 and if the frequency ever matches we know we’ve found our substring permutation and can return true. If we reach the end and we haven’t found it we return false

How do we actually do the frequency match though?

• We could just check and see if all values match and since we are guaranteed lowercase letters this is O(26) => O(1)
• So we don’t need to do any fancy number of matches

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        #Create the freq map
        freq_map = Counter(s1)

        check_freq_map = Counter(s2[:len(s1)])



        l = 0
        r = len(s1) - 1
        while r < len(s2):
            if freq_map == check_freq_map:
                return True
            r += 1
            if r >= len(s2):
                return False
            check_freq_map[s2[r]] += 1
            check_freq_map[s2[l]] -= 1
            l += 1
        return False

https://neetcode.io/problems/eating-bananas/question?list=neetcode150

Ok Metric:

• Return minimum of k such that we can eat all bananas within h
  • What does it mean to eat at rate k?
    • So eating at rate k means each pile will take math.ceil(x/k) hours
    • Eg if k = 2 5/2 = 2.5 => 3 hours
    • So then you get number of hours to eat all bananas is
    • for x in piles:
      • total_time += math.ceil(x/k)
    • total_time < h

What are the ranges? If no constraint she can eat at k = 1 so 1 banana per hour => sum(piles) = total_hours If as fast as possible it would be each one only takes 1 hour so max(piles) = k

so our range becomes [1, max(piles)]

So we need to find the minimum value such that when we calculate total_hours <= h

Ok so we could do the brute force way and just iterate through the list from 1 -> max(piles) and for the first value where total_time <= h we just return that value

But we could search this space more efficiently with binary search as well

Process basically becomes

1. Select a k
2. Calculate hours
3. if hours > h
   1. New range is (k max(piles)]
4. if hours <= h
   1. record min_k
   2. New range is [1,k)
5. Return min k

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:

        def calculate_hours(k):
            total_hours = 0
            for x in piles:
                total_hours += math.ceil(x/k)
            return total_hours

        min_rate = 1
        max_rate = max(piles)
        min_k = max(piles)
        # min_rate = 2
        # max_rate = 1
        # min_k = 2
        # h = 9
        # middle = 1
        # hours = 1 + 4 + 3 + 2 = 10
        while min_rate <= max_rate:
            middle = (max_rate + min_rate) // 2

            hours = calculate_hours(middle)
            if hours > h:
                min_rate = middle + 1
            else:
                min_k = min(min_k, middle)
                max_rate = middle - 1

        return min_k