# CSPT25 Lecture 7
## Jewels and Stones

class Solution:
    """
    Understand
    jewels = "aA", stones = "aAAbbbb" --> 3
    jewels = "z", stones = "ZZ" --> 0
    jewels = "aA", stones = "aAA" --> 3
    Plan
    Put all characters in jewels in a set, then for each stone check if it's in that set
    Return the number of stones that are in that set
    Runtime: O(n) where n = len(jewels) == len(stones)
    Space: O(n) where n = len(jewels)
    """
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        j = set(jewels) # O(n) where n = len(jewels)
        numJewels = 0
        for stone in stones: # O(m) where m = len(stones)
            if stone in j: # n
                numJewels += 1
        return numJewels

## Smaller Numbers

class Solution:
    """
    nums = [8,1,2,2,3]
    output = [4,0,1,1,3]
    
    nums = [1,1,1,1]
    output = [0,0,0,0]
    
    nums = [4,3,2,1]
    output = [3,2,1,0]
    
    nums = [1,2,3,4]
    output = [0,1,2,3]
    
    Hint: You can solve this using sorting (.sort() or sorted())
    Sorting takes O(nlogn) time
    
    Brute-Force Approach
    O(n^2) time. For each number, check all other numbers to see how many
    are less than it. Append the result to an output list.
    
    Sorting
    Sort the input list, then build a dictionary from the sorted list.
    Where the key is the element and value is how many elements are smaller than it.
    Lastly, walk through the original list and use the dictionary created to 
    construct the output list
    Runtime: O(nlogn)
    Space: O(n)
    """
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sortedNums = sorted(nums) # nlogn
        numMap = {}
        for (i, num) in enumerate(sortedNums): # n
            if num not in numMap:
                numMap[num] = i
        res = []
        for num in nums: # n
            res.append(numMap[num])
        return res

## Keyboard Row

class Solution:
    """
    words = ["Hello","Alaska","Dad","Peace"]
    output = ["Alaska","Dad"]
    
    words = ["Hello", "Peace"]
    output = []
    
    words = ["ALASkA", "DAd", "tip", "x"]
    output = ["ALASkA", "DAd", "tip", "x"]
    
    Hint: You can do this with 3 sets
    Plan
    Have 3 sets, one for each row. Go through each word, start
    with the first letter and search which set it belongs to.
    Then check if the other letters in that word all belong in that same set.
    If so, then append it to the output list.
    words = ["ALASkA", "DAd", "tip", "x"]
    res = ["ALASkA", "DAd", "tip", "x"]
    Runtime: O(n * k) where n = len(words), k = max(len(word))
    Space: O(n) where n = len(words)
    """
    def findWords(self, words: List[str]) -> List[str]:
        rows = [set(["q","w","e","r","t","y","u","i","o","p"]), set(["a","s","d","f","g","h","j","k","l"]), set(["z","x","c","v","b","n","m"])]
        res = []
        for word in words: # n where n = len(words)
            rowFirstLetterBelongsTo = set()
            for row in rows: # 1
                if word[0].lower() in row:
                    rowFirstLetterBelongsTo = row
                    break
            allLettersAreInSameRow = True
            for i in range(1, len(word)): # k where k = len(word)
                if word[i].lower() not in rowFirstLetterBelongsTo:
                    allLettersAreInSameRow = False
                    break
            if allLettersAreInSameRow:
                res.append(word)
        return res