CDFX01 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Link

Practice Link

DIFFICULTY:

Easy

PREREQUISITES:

Implementation

PROBLEM:

Given two strings S1 and S2 of equal lengths. Find the Lexicographically smaller string considering letters case insensitive.

EXPLANATION:

Input strings can contain both uppercase or lowercase letters. But we have to consider letters case insensitive while comparing the strings. So, first of all convert both strings to either LOWERCASE or UPPERCASE. After that process each character of the stings simultaneously and compare their ASCII values.

Read about Lexicographical Order [here] 3

TIME COMPLEXITY:

O(N) per testcase, where N is length of the string.

SOLUTION:

To be Updated Soon

2

In python, we can do it with O(1) time complexity per testcase. :slight_smile:

3

Can you please explain me how can we do it in O(1) ?

4

See this solution. This can be done in some other languages including JAVA too.
https://www.codechef.com/viewsolution/9515912

5

I would suggest you to please once go through the implementation of comparison operator and study how it works in case of strings. It’s complexity is O(N) not O(1). It’s ok to use Library functions. But you should also have a fair idea of what’s going behind the scenes. Also, Conversion of a string to lower case itself is a O(N) operation where N is length of string.

Read about the complexities of operators here : https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

6

I am new to python that’s why I wasn’t aware of this. Thanks very much for the information. :slight_smile:

7

import sys

str1=sys.argv[1]

str2=sys.argv[2]

ar1 =list(str1.lower())

ar2 =list(str2.lower())

for i in range(0,len(ar1)-1):

if ord(ar1[i])>ord(ar2[i]):

    sys.exit("S2 is smaller")

if ord(ar1[i])<ord(ar2[i]):

    sys.exit("S1 is smaller")

print “Both are equal”