<reponame>thrastarson/algos
import itertools
from utils import sort_string, build_string

#The following problems are from the book Cracking the Coding Interview
#by <NAME>. I reserve no rights for them.

#Problem 1.1
#Implement an algorithm to determine if a string has all unique characters.
#What if you cannot use an external data structure?
def is_unique(w):
    """
    First solution uses a dictionary or hash table
    to record previously unseen characters in w.
    Runs in O(n).
    """
    chars = {}
    for c in w:
        if c in chars:
            return False
        chars[c] = True
    return True

def is_unique2(w):
    """
    Second solution sorts w and scans to see if any
    adjacent characters are the same.
    Runs in O(n*log(n)).
    """
    if len(w) <= 1:
        return True

    w_sorted = sort_string(w)
    i = 0
    while i < len(w_sorted) - 1:
        if w_sorted[i] == w_sorted[j]:
            return False
        i += 1
    return True

#Problem 1.2
#Given two strings, write a method to decide if one is a permutation
#of the other.
def check_permutation(u, v):
    """
    First solution uses a handy function from the itertools library.
    Runs in O(n!) worst-case time.
    """
    for permutation in itertools.permutations(u):
        if v == permutation:
            return True
    return False

def check_permutation2(u, v):
    """
    Second solution walks through both u and v and builds a dict
    of distinct characters and their counts for each. 
    It then compares the counts of characters between them.
    Runs in O(max(n, m)) where n = len(u) and m = len(v).
    """
    u_chars = {}
    for c in u:
        try:
            u_chars[c] += 1
        except KeyError:
            u_chars[c] = 1

    v_chars = {}
    for d in v:
        try:
            v_chars[d] += 1
        except KeyError:
            v_chars[d] = 1

    if sum(u_chars.values()) != sum(v_chars.values()):
        #u and v are not of the same length.
        return False

    for c in u:
        c_count_in_u = u_chars[c]
        c_count_in_v = v_chars.get(c, 0)
        if c_count_in_u != c_count_in_v:
            return False

    return True

#Problem 1.3
#Write a method to replace all spaces in a string with '%20'. You may assume
#the string has sufficient space at the end to hold additional characters,
#and that you are given the true length of the string.
def urlify(w, length):
    """
    First solution uses python built-in functions
    in a simple one-liner.
    """
    return w.strip().replace(' ', '%20')

def urlify2(w, length):
    """
    Second solution walks through the string once and detects words
    and spaces, adding appropriate strings to a list. It then uses
    a StringBuilder-like method to efficiently concatenate them.
    Runs in O(n).
    """
    chars = []
    while i < len(w):
        c = w[i]
        if c == ' ':
            chars.append('%20')        
        else:
            chars.append(c)
        i += 1
    url_w = build_string(chars)
    return url_w

#Problem 1.4
#Given a string, write a function to check if it is a permutation
#of a palindrome. A palindrome is a word or phrase that is the same
#backwards and forwards. A permutation is a rearrangement of letters.
#The palindrome does not need to be limited to just dictionary words.
def palindrome_permutation(w):
    """
    This solution counts how often each distinct character appears
    in w. Checking for a possible palindrome then proceeds in two
    slightly different cases, depending on whether w is of even
    or odd length.
    """
    w = w.strip().replace(' ', '')
    chars = {}
    for c in w:
        try:
            chars[c] += 1
        except KeyError:
            chars[c] = 1

    if len(w) % 2 == 0:
        #Check if there is an even number
        #of every character in w.
        return all(x % 2 == 0 for x in chars.values()) 
    else:
        #Check if there is an even number
        #of every character in w,
        #except for exactly one character.
        found_odd = False
        for c in chars:
            if chars[c] % 1 == 0:
                if not found_odd:
                    found_odd = True
                else:
                    return False
        
        if found_odd:
            return True
        else:
            return False

#Problem 1.5
#There are three types of edits that can be performed on strings:
#remove a character, or replace a character. Given two strings,
#write a function to check if they are one edit (or zero edits) away.
def one_away(u, v):
    if u == v:
        return True

    if abs(len(u) - len(v)) > 1:
        return False

    if len(u) < len(v):
        #set u to be the longer string
        v, u = u, v

    found_edit = False
    i = 0
    j = 0
    while i < len(u) and j < len(v):
        if u[i] == v[j]:
            i += 1
            j += 1
        else:
            if len(u) == len(v):
                if found_edit:
                    return False
                else:
                    found_edit = True
                    i += 1
                    j += 1
            else:
                if found_edit:
                    return False
                else:
                    found_edit = True
                    i += 1
    return True
                
#Problem 1.6
#Implement a method to perform basic string compression using
#the counts of repeated characters. For example, the string
#aabcccccaaa would become a2b1c5a3. If the compressed string
#would not become smaller than the original string, your method
#should return the original string. You can assume the string
#has only uppercase and lowercase letters (a-z).
def string_compression(w):
    """
    This solution runs in O(n).
    """
    if len(w) <= 1:
        return w

    substrings = []
    prev_char = w[0]
    char_count = 1
    for char in w[1:]:
        if prev_char == char:
            char_count += 1
        else:
            substrings.append('%s%s' % (prev_char, char_count))
            char_count = 1
            prev_char = char

    substrings.append('%s%s' % (prev_char, char_count))

    compression = ''.join(substrings)
    if len(compression) < len(w):
        return compression
    else:
        return w

#Problem 1.7
#Given an image represented by an NxN matrix, where each pixel
#in the image is 4 bytes, write a method to rotate the image
#by 90 degrees. Can you do this in place?
def rotate_matrix(matrix):
    """
    This solution works by working on the square matrix
    from the outside in, switching one row with the row
    to its right until a full circle is done, then proceeds
    to do the same with its inner circle.
    This solution runs in O(n^2).
    """
    
    n = len(matrix)
    if n == 0 or len(matrix[0]) != n:
        return False

    for layer in range(n // 2):
        first = layer
        last = n - 1 - layer
        for i in range(first, last):
            offset = i - first
            
            #save top
            top = matrix[first][i]

            # left -> top
            matrix[first][i] = matrix[last-offset][first]

            #bottom -> left
            matrix[last-offset][first] = matrix[last][last-offset]

            #right -> bottom
            matrix[last][last-offset] = matrix[i][last]

            #top -> right
            matrix[i][last] = top

    return True

#Problem 1.8
#Write an algorithm such that if an element in an MxN matrix is 0, 
#its entire row and column are set to 0.
def zero_matrix(matrix):
    """
    This solution runs in O(n^2) because it necessarily must look
    at every element in the matrix.
    """
    n = len(matrix)
    if n == 0:
        return True

    m = len(matrix[0])
    if m == 0:
        return True

    zero_rows = set()
    zero_columns = set()
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 0:
                zero_rows.add(i)
                zero_columns.add(j)
    
    for i in zero_rows:
        for j in range(m):
            matrix[i][j] = 0

    for i in range(n):
        for j in zero_columns:
            matrix[i][j] = 0

    return True

#Problem 1.9
#Assume that you have a method isSubstring which checks if one word is a substring
#of another. Given two strings, s1 and s2, write code to check if s2 is a rotation
#of s1 using only one call to isSubstring (e.g. "waterbottle" is a rotation
#of "erbottlewat".
def string_rotation(s1, s2):
    s1s1 = s1 + s1
    return s2 in s1s1
