highest_value_palindrome.py

# source: https://www.hackerrank.com/challenges/richie-rich/problem
# video: https://youtu.be/fcf4gy5V3L4
def count_mismatches(string_1, string_2):
    """
    Returns count of mismatches between two given strings
    """
    assert len(string_1) == len(string_2)
    count = 0
    for char_1, char_2 in zip(string_1, string_2):
        count += char_1 != char_2
    return count


def parse_palindrome_parts(s):
    """
    Returns left, middle (if exists, None otherwise), and reversed right side
    of given string s  
    """
    has_middle = len(s) % 2 != 0
    center_i = len(s) // 2
    left_part = s[:center_i]
    middle = s[center_i] if has_middle else ''
    right_part = s[center_i+1:] if has_middle else s[center_i:]
    return left_part, middle, right_part[::-1]


NINE = '9'


def highestValuePalindrome(s, n, k):
    # parse out palindrome parts (ex. "00123" => "00", "1", "32")
    left_part, middle_part, right_rev_part = parse_palindrome_parts(s)  # O(n)

    # determine number of mismatches preventing innate palindrome
    mismatches = count_mismatches(left_part, right_rev_part)  # O(n)

    # short-circuit: if k alterations >= length of string, use all 9's
    if k >= n:
        return NINE * n

    # if k alterations is too small to handle mismatches
    if k - mismatches < 0:
        return '-1'

    final_left = ''
    # Going outer to inner, we build new string while optimizing for largest number...
    for left_char, right_char in zip(left_part, right_rev_part):  # O(n)
        is_mismatch = left_char != right_char
        num_of_non_9_chars = int(left_char != NINE) + int(right_char != NINE)
        next_char = None
        ### MAIN LOGIC ###
        # Moving from outer to inner characters...
        if not is_mismatch:
            # if numbers match, we have opportunity to use "surplus" alterations

            # By default, use current char
            next_char = left_char  # same as right_char!
            # if both characters are NOT '9's AND there are 2 alterations available...
            if num_of_non_9_chars > 0 and k - 2 >= mismatches:
                # NOTE: "available alterations" means we still have enough to handle
                # mismatches, since we need AT MOST 1 alteration to handle a mismatch
                k -= 2
                next_char = NINE
        else:  # is_mismatch
            # if numbers don't match, we will try to replace with as many 9's as possible
            if num_of_non_9_chars == 1:
                # if only one char is a '9' => replace other with a '9'
                k -= 1
                mismatches -= 1
                next_char = NINE
            else:  # both chars are NOT '9'
                # Will try to swap both to '9' IF 2 available alterations
                # Otherwise, we will try to convert smaller num to larger num (1 alteration)
                # Else, no alterations left for mismatch => return '-1'
                if k-2 >= mismatches-1:  # 2 alterations available
                    # replace both chars with '9'
                    k -= 2
                    mismatches -= 1
                    next_char = NINE
                else:  # 1 alteration availalbe
                    # use larger number to replace smaller
                    larger_num = max(int(left_char), int(right_char))
                    k -= 1
                    mismatches -= 1
                    next_char = str(larger_num)

        final_left += next_char
    # if alterations remain AND a middle part exists, just make middle part a '9'
    if k and middle_part:
        middle_part = NINE

    return final_left + middle_part + final_left[::-1]
    # Total Time Compexity: O(n) * 3 = O(n)