# Sprint 1 Module Project 3
## csLongestPossible

"""
This solution uses a set. Sets only contain unique elements,
so adding an existing character in a set doesn't do anything.

1. We add all characters in both strings to the set. This takes
care of duplicate characters for us
2. Sets are unordered, so we first transform them into a list
3. We sort the list and return it

Runtime: O(nlogn), where n = number of characters in str_1 + str_2
Space: O(n), where n = number of characters in str_1 + str_2
"""
def csLongestPossible(str_1, str_2):
    characterSet = set(str_1 + str_2)
    sortedList = sorted(list(characterSet)) # you can assume most sorting functions are nlogn time, where n =  number of elements
    return ''.join(sortedList)

## csSortedTwoSum

"""
We did a similar one in lecture and that solution works here as well.
Note: Since the input here is sorted, you can also use Binary Search 
(we'll talk about this in a future lecture).

Runtime: O(n)
Space: O(n)
"""

def csSortedTwoSum(numbers, target):
    d = {}
    for i, num in enumerate(numbers):
        if target - num in d:
            return (d[target - num], i)
        d[num] = i

## csFindAddedLetter

"""
Sort both strings and iterate through both strings to see which character was added
Runtime: O(nlogn) where n is the length of str_2
Space: O(n) where n is the length of str_2
"""
def csFindAddedLetter(str_1, str_2):
    sortedStr1 = sorted(str_1)
    sortedStr2 = sorted(str_2)
    for i in range(len(sortedStr2)):
        if i >= len(sortedStr1) or sortedStr1[i] != sortedStr2[i]:
            return sortedStr2[i]

## csFirstUniqueChar

"""
Do a pass and count how many times each character appears
Do another pass and return the first character that has a count of 1
Runtime: O(n)
Space: O(n)
"""
def csFirstUniqueChar(input_str):
    charCount = {}
    for char in input_str:
        if char in charCount:
            charCount[char] += 1
        else:
            charCount[char] = 1
    for (i, char) in enumerate(input_str):
        if charCount[char] == 1:
            return i
    return -1