Codeforces Problem: Azamon Web Services: Solution in Python

Problem

Given two string, find if using max one swap of characters, the first string is lexicographically smaller than the other string.

Solution

The logic is as follows:

  1. Create an index map of each character in the string A.
  2. Compare String A & String B, character-by-character.
  3. If characters are the same, move to the next character.
  4. If char ‘c’ in string A is larger than char ‘d’ in String B
  5. Find if there is a character ‘x’ in String A that is smaller than ‘d’.
  6. Swap ‘c’ & ‘x’
  7. If there was one such swap, we are done.
  8. Else, not possible to make String A lexicographically smaller than String B.
def find_lexical_smaller_string(str1, str2):
    pass
    # check 1: proper prefix
    if str2.find(str1) == 0 and len(str1) != len(str2):
        return "proper prefix"
   
    # check 2: string2 is lexicographically smaller
    is_impossible = True
    for c,d in zip(str1, str2):
        # print(c,d)
        if c < d:
            is_impossible = False
            break
        
    if is_impossible:
        return "---"
    
    
    return find_and_swap_pair(str1, str2)


def find_and_swap_pair(str1, str2):
    char_set = {}
    index = 0
    did_swap = False
    
    for c in str1:
        if c in char_set:
            char_set[c].append(index)
        else:
            char_set[c] = [index]
        index += 1
    
    print("char_set={}".format(char_set))
    index = 0

    s1 = list(str1)
    s2 = list(str2)
    
    for c,d in zip(s1, s2):
        if c == d:
            index += 1
            continue
        
        if c > d:
            ch = find_char_in_range(char_set, index, d)
            print("ch={}".format(ch))
            s1[index], s1[ch] = s1[ch], s1[index]
            did_swap = True
            break
        
        index += 1
        
    if did_swap:
        print("s1={}".format(s1))
        new_str1 = ''.join(s1)
        return new_str1
    
    return None


def find_char_in_range(char_set, index, high_limit):
    ascii_target = ord(high_limit)
    print("ascii_target={}-{}".format(high_limit, ascii_target))
    
    ascii_target -= 1
    
    while ascii_target >= 0:
        c = chr(ascii_target)
        ascii_target -= 1

        if c in char_set:
            index_list = char_set[c]
            min_index = find_minimum_index(index_list, index)
            if min_index < 0:
                continue
            else:
                break

    if min_index >= 0:
        print("min_index={}".format(min_index))
    return min_index
    
        
def find_minimum_index(index_list, index):
    if len(index_list) > 0:
        print("index_list={}".format(index_list))
        min_index = index_list[0]
        del index_list[0]
        return min_index
    return -1
        
print (find_lexical_smaller_string('AON', 'AONE'))
print (find_lexical_smaller_string('AZAMON', 'APPLE'))
print (find_lexical_smaller_string('AZAMON', 'AAAAAAAAAAPPLE'))

Execution

$ python lexical_strings.py                                                                                                      
proper prefix
char_set={'A': [0, 2], 'Z': [1], 'M': [3], 'O': [4], 'N': [5]}
ascii_target=P-80
index_list=[4]
min_index=4
ch=4
s1=['A', 'O', 'A', 'M', 'Z', 'N']
AOAMZN
---

Reference

BlinkBlank

Knowledge is the seed of wisdom.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.