Medium Interview Question

def keypad_string(keys):

    result = []
    word = []
    keypad = {
        "1" : [""],
        "2" : ["a", "b", "c"],
        "3" : ["d", "e", "f"],
        "4" : ["g", "h", "i"],
        "5" : ["j", "k", "l"],
        "6" : ["m", "n", "o"],
        "7" : ["p", "q", "r", "s"],
        "8" : ["t", "u", "v"],
        "9" : ["w", "x", "y", "z"],
        "0" : [" "],
        }
    keypad = build_keypad()

    for i, val in enumerate(keys):
        word.append(val)
        if i==len(keys)-1 or val != keys[i+1] or len(word) == len(keypad.get(val)):
            result.append(keypad.get(val)[len(word) - 1])
            word = []
    return ''.join(result)

def build_keypad():
    import string
    possible_letters = list(string.ascii_lowercase)
    keypad = {}
    keypad["0"] = [" "]
    keypad["1"] = [""]

    w = 0
    for i in range(2, 10):
        if i in {7, 9}:
            keypad[str(i)] = possible_letters[w:w+4]
            w += 4
        else:
            keypad[str(i)] = possible_letters[w:w+3]
            w += 3
    return keypad

def keypad_string(keys):
    """
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1        | 2 (abc) | 3 (def)  |
    | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |     *    | 0 ( )   |     #    |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''
    >>> keypad_string("2222")
    'ca'
    >>> keypad_string("12345")
    'adgj'
    """

    map_dic = {
        "1": "",
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
        "0": " ",
        "*": "",
        "#": "",
    }

    def return_letter_3(key_pressed, i):
        if keys.count(key_pressed, i, i + 3) == 3:
            letter = map_dic[key_pressed][2:3]
            i += 3
        elif keys.count(key_pressed, i, i + 2) == 2:
            letter = map_dic[key_pressed][1:2]
            i += 2
        elif keys.count(key_pressed, i, i + 1) == 1:
            letter = map_dic[key_pressed][0:1]
            i += 1
        return letter, i

    def return_letter_4(key_pressed, i):
        if keys.count(key_pressed, i, i + 4) == 4:
            letter = map_dic[key_pressed][3:4]
            i += 4
        elif keys.count(key_pressed, i, i + 3) == 3:
            letter = map_dic[key_pressed][2:3]
            i += 3
        elif keys.count(key_pressed, i, i + 2) == 2:
            letter = map_dic[key_pressed][1:2]
            i += 2
        elif keys.count(key_pressed, i, i + 1) == 1:
            letter = map_dic[key_pressed][0:1]
            i += 1
        return letter, i

    enum_keys = enumerate(keys)
    decoded_string = ""
    letter = ""
    i = 0
    while i != len(keys):
        # breakpoint()
        if keys[i] == "2":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "3":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "4":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "5":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "6":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "8":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "7":
            letter, i = return_letter_4(keys[i], i)
        elif keys[i] == "8":
            letter, i = return_letter_4(keys[i], i)
        elif keys[i] == "0":
            letter = " "
            i += 1
        else:
            i += 1

        decoded_string += letter

    return decoded_string

def keypad_strings(keys):
    numbers_dict = defaultdict()
    char = 97
    for _ in range(10):
        if _ == 7 or _ == 9:
            key = 4
            numbers_dict[_] = (char, key)
            char += key
        elif _ == 0 or _ == 1:
            numbers_dict[_] = (0, 0)
        else:
            key = 3
            numbers_dict[_] = (char, key)
            char += key
    counter = 0
    result = ''
    for i, key in enumerate(keys):
        if numbers_dict[int(key)][0] == 0:
            continue
        if i > 0 and key == keys[i - 1]:
            counter += 1
        else:
            counter = 0
        char_int = numbers_dict[int(key)][0] + counter
        if counter < numbers_dict[int(key)][1]:
            if counter == 0:
                result += chr(char_int)
            else:
                result = result[:-1] + chr(char_int)
        else:
            counter = 0
            result += chr(char_int)

    return result

from collections import deque
import string


def _map_keys() -> dict:
    """ Map keypad numbers to ascii characters

    Returns:
        dict: Maps key number to a list of characters
    """

    FOUR_CHARS = {7, 9}
    key_map = {'0': [" "], '1': []} # Hard code special keys
    start, stop = 0, 3 # Set the initial slice indexes

    def _inc_slice_index(n):
        """ Increment the start:stop slicing indexes by n """
        nonlocal start, stop
        start += n
        stop += n

    for i in range(len(key_map), len(string.digits)):
        key = str(i)
        if i in FOUR_CHARS:
            key_map[key] = list(string.ascii_lowercase[start:stop + 1])
            _inc_slice_index(4)
        else:
            key_map[key] = list(string.ascii_lowercase[start:stop])
            _inc_slice_index(3)

    return key_map


def _create_string(seq) -> str:
    """ Create a string from a list of integers. The integer maps to a 
    possible list of chars.  The frequency (length of sequence) determines
    the index of the character to use.  
    For example: [4, 4, 4], length 3, maps
    to the character 'i'; the 3rd character in the list.

    Args:
        sequence (list[[str]]): Eg: ['2','2'],['0'], ['2']]

    Returns:
        str: A string from the sequence of key presses.
    """

    # Get a key mapping.
    keymap = _map_keys()

    # Build the string from the key press sequence.
    str_seq = ""
    for freq in seq:
        str_seq += keymap[freq[0]][len(freq) - 1]
    return str_seq


def keypad_string(keys):
    '''
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1        | 2 (abc) | 3 (def)  |
    | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |     *    | 0 ( )   |     #    |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''
    >>> keypad_string("#")
    Traceback (most recent call last):
    AssertionError: Invalid Key: Acceptable keys 0123456789
    '''

    MAX_KEYPRESS_COUNT = 3  # Max number of times a key can be pressed
    IGNORE_KEYS = {'1'}     # Set of keys that do nothing and will be ignored.

    if not keys:
        return ''

    keys_q = deque(keys)
    seq, buf, count = [], [], 0

    while(keys_q):
        key_pressed = keys_q.popleft()  # popleft=O(1) vs pop(0)=O(n)
        assert key_pressed in string.digits, "Invalid Key: Acceptable keys " + string.digits

        # Ignore certain keys, and service the next key press
        if key_pressed in IGNORE_KEYS: continue

        count += 1
        # Append the pressed key to the buffer.  If the key has been pressed 3 times, the max
        # sequence has been reached, and must be appened to the sequence list.
        if (not buf or buf and key_pressed == buf[0]) and count < MAX_KEYPRESS_COUNT:
            buf.append(key_pressed)
        else:
            seq.append(buf)
            buf = []
            buf.append(key_pressed)
            count = 0

    # Append the buffer if it contains valid key presses.
    if buf: seq.append(buf)
    return _create_string(seq)

def keypad_string(keys):
        '''
        Given a string consisting of 0-9,
        find the string that is created using
        a standard phone keypad
        | 1        | 2 (abc) | 3 (def)  |
        | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
        | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
        |     *    | 0 ( )   |     #    |
        You can ignore 1, and 0 corresponds to space
        >>> keypad_string("12345")
        'adgj'
        >>> keypad_string("4433555555666")
        'hello'
        >>> keypad_string("2022")
        'a b'
        >>> keypad_string("")
        ''
        >>> keypad_string("111")
        ''
        '''
        mydict = []
        mystr = ''
        res = ''
        for c in keys:
            if (c in mystr) or mystr == "":
                mystr += c
            else:
                mydict.append(mystr)
                mystr = c
        mydict.append(mystr)
        for c in mydict:
            #print(f"{c} {len(c)}")
            if '0' in c:
                res += " "*len(c)
            if '1' in c or '*' in c or '#' in c:
                continue
            if '2' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'c'*q
                if r == 1:
                    res += 'a'
                if r == 2:
                    res += 'b'
            if '3' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'f'*q
                if r == 1:
                    res += 'd'
                if r == 2:
                    res += 'e'
            if '4' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'i'*q
                if r == 1:
                    res += 'g'
                if r == 2:
                    res += 'h'
            if '5' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'l'*q
                if r == 1:
                    res += 'j'
                if r == 2:
                    res += 'k'
            if '6' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'o'*q
                if r == 1:
                    res += 'm'
                if r == 2:
                    res += 'n'
            if '7' in c:
                r = len(c) % 4
                q = len(c) // 4
                res += 's'*q
                if r == 1:
                    res += 'p'
                if r == 2:
                    res += 'q'
                if r == 3:
                    res += 'r'
            if '8' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'v'*q
                if r == 1:
                    res += 't'
                if r == 2:
                    res += 'u'
            if '9' in c:
                r = len(c) % 4
                q = len(c) // 4
                res += 'z'*q
                if r == 1:
                    res += 'w'
                if r == 2:
                    res += 'x'
                if r == 3:
                    res += 'y'
        return res

from itertools import groupby
import string


KEYPAD_MAP: dict[str, list[str]] = {
    "2": list("abc"),
    "3": list("def"),
    "4": list("ghi"),
    "5": list("jkl"),
    "6": list("mno"),
    "7": list("pqrs"),
    "8": list("tuv"),
    "9": list("wxyz"),
    "0": [" "],
}

DIGIT_SET = set(string.digits)


def keypad_string(keys: str) -> str:
    """
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1        | 2 (abc) | 3 (def)  |
    | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |     *    | 0 ( )   |     #    |
    You can ignore 1, and 0 corresponds to space

    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''
    >>> keypad_string("9442877770887")
    'whats up'
    >>> keypad_string("555")
    'l'
    >>> keypad_string("000")
    '   '
    >>> keypad_string("0000a")
    Traceback (most recent call last):
    AssertionError: Input must be a digit: a
    >>> keypad_string("5055")
    'j k'
    """
    if keys == "":
        return ""
    for char in keys:
        assert char in DIGIT_SET, f"Input must be a digit: {char}"

    grouped = [list(group) for char, group in groupby(keys)]  # O(n)
    # breakpoint()

    output = list()

    for key_pattern in grouped:
        digit = key_pattern[0]

        # special case for 1
        if digit == "1":
            continue
        remaining_length = len(key_pattern)

        characters = KEYPAD_MAP[digit]

        # determine how many characters are actually produced by group
        while remaining_length > len(characters):
            # if more keys pressed than characters, this means there must be multiple letters
            # grab the last character, decrement the length, and continue
            output.append(characters[-1])
            remaining_length -= len(characters)

        if remaining_length > 0:
            output.append(characters[remaining_length - 1])

    return "".join(output)

def keypad_string(keys):
    word = ''
    grid = " ,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz".split(',')

    # Create comme separated string
    newstr = ''
    for i, k in enumerate(keys):
      if(i == 0 or k != keys[i-1]):
        newstr += ','
      newstr += k

    for gr in newstr[1:].split(','):
      if(len(gr)>0 and gr[0] in '023456789'):
          key, count = int(gr[0]), len(gr)
          max = len(grid[key])
          remain = count % max
          word = word + count // max * grid[key][max-1]
          if( remain > 0):
            word = word + grid[key][remain-1]

    return word

def keypad_string(keys):
    '''
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1         | 2 (abc) | 3 (def)  |
    | 4 (ghi)   | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs)  | 8 (tuv) | 9 (wxyz) |
    | *         | 0 ( )   | #        |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    '''

    KEY_MAPPING = {"1": "",
                   "2": "abc",
                   "3": "def",
                   "4": "ghi",
                   "5": "jkl",
                   "6": "mno",
                   "7": "pqrs",
                   "8": "tuv",
                   "9": "wxyz",
                   "0": " "}

    final_str = ""
    def str_builder(digit, count):
        str_builder = ""
        mapped_chars_list = list(KEY_MAPPING[digit]) # 9 ["w", "x", "y", "z"]
        size_of_mapping = len(KEY_MAPPING[digit]) # 4
        remainder = count%size_of_mapping
        rounds = count//size_of_mapping
        if rounds > 0:
            for _ in range(rounds):
                str_builder += mapped_chars_list[size_of_mapping - 1] 
            if remainder > 0:
                str_builder += mapped_chars_list[remainder - 1] 
        else: 
            str_builder += mapped_chars_list[count - 1] 

        return str_builder

    left = right = 0
    while right < len(keys):
        key = keys[left]
        if key == "1" or key == "0":
            final_str += KEY_MAPPING[key]
            left +=1
            right +=1
        else:
            key_count = 0
            while right < len(keys):
                if key == keys[right]:
                    key_count += 1
                else:
                    left = right
                    break
                right +=1


            final_str += str_builder(key, key_count)

    return final_str