# 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
del index_list
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': , 'M': , 'O': , 'N': }
ascii_target=P-80
index_list=
min_index=4
ch=4
s1=['A', 'O', 'A', 'M', 'Z', 'N']
AOAMZN
---
``````

### Reference

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