# CSPT27 Lecture 7
## Jewels & Stones

class Solution:
    """
    Understand
    jewels = "aA", stones = "aAAbbbb"
    output = 3
    
    jewels = "z", stones = "ZZ"
    output = 0
    
    jewels = "z", stones = "zzz"
    output = 3
    
    Plan
    Brute-force
    For each stone, check if it's a jewel. Keep track of the number
    of jewels found.
    Runtime: O(n^2)
    Space: O(1)
    
    Another approach
    Transform jewels into a set. Then check if each stone is in that set.
    Keep track of num jewels found.
    Runtime: O(m + n) where m = len(jewels), n = len(stones)
    Space: O(m)
    """
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        j = set(jewels) # O(m) where m = len(jewels)
        numJewels = 0
        for s in stones: # O(n) where n = len(stones)
            if s in j: # O(1)
                numJewels += 1
        return numJewels

## Numbers Smaller than Number

class Solution:
    """
    Understand
    nums = [8,1,2,2,3]
    output = [4,0,1,1,3]
    
    nums = [1,1,1]
    output = [0,0,0]
    
    nums = [4,3,2,1]
    output = [3,2,1,0]
    
    nums = [1,2,3]
    output = [0,1,2]
    
    Plan
    Brute-force Approach
    For each number, iterate through all other numbers
    and keep track of how many elements are < it.
    Runtime: O(n^2)
    Space: O(n)
    
    Hint: Use sorting + hash-and-store
    Runtime: O(nlogn)
    Space: O(n)
    """
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sortedNums = sorted(nums)
        numMap = {}
        for i, num in enumerate(sortedNums):
            if num not in numMap:
                numMap[num] = i
        res = []
        for num in nums:
            res.append(numMap[num])
        return res

## Keyboard Row

class Solution:
    """
    Understand
    words = ["Hello","Alaska","Dad","Peace"]
    output = ["Alaska","Dad"]
    
    words = ["Hello","Peace"]
    output = []
    
    words = ["Dad", "YOU", "z"]
    output = ["Dad", "YOU", "z"]
    
    Plan
    Create a set for each row
    Go through each word, find out which row the first
    character belongs to. Then check if all other chars
    are also in that same set. Early terminate if
    you find a character that's not in that set and go 
    to the next word. If you go through all characters in that
    word, then append that to your output list.
    Runtime: O(number of words * max(number of letters in word))
    Space: O(number of 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 = [] # n
        for word in words:
            rowFirstLetterBelongsTo = set()
            for row in rows:
                if word[0].lower() in row:
                    rowFirstLetterBelongsTo = row
                    break
            allLettersAreInSameRow = True
            for i in range(1, len(word)): # m where m = len(longestWord)
                if word[i].lower() not in rowFirstLetterBelongsTo:
                    allLettersAreInSameRow = False
                    break
            if allLettersAreInSameRow:
                res.append(word)
        return res