String Mania

Easy
0/40
Average time to solve is 5m
profile
Contributed by
20 upvotes

Problem statement

Rohit love strings. But he has many strings with him, and he is confused about which one he loves more. So he decided to come up with a scoring system for the strings. The scoring system took two strings as input, let's call them ‘STR1’ and ‘STR2’ of length ‘N’ and length ‘M’ respectively.

The system will return ‘1’ if ‘STR1’ is better than ‘STR2’.

The system will return ‘0’ if ‘STR1’ is the same as ‘STR2’.

The system will return ‘-1’ if ‘STR2’ is better than ‘STR1’.

To decide which string is better he followed the below steps.

Let’s suppose there exists a index ‘i’ such that ‘0’ <= ‘i’ < ‘min(N,M)’ and for all ‘j<i’, ‘STR1[j]’ is equal to ‘STR2[j]’, and ‘STR1[i] != STR2[i]’.

Then if ‘STR1[i]>STR2[i]’, ‘STR1’ is better otherwise if ‘STR2[i]>STR1[i]’, ‘STR2’ is better,

And if there doesn’t exist any such ‘i’ then if ‘N>M’, ‘STR1’ is better,

And if ‘N<M’, ‘STR2’ is better, and if ‘N’ is equal to ‘M’, both strings are the same.

But Rohit has so many strings, so he doesn’t have time to go through all strings, So being his friend can you help him automate this process?.

EXAMPLE : 
Input: ‘N’ = 3, ‘M’ = 4, ‘STR1’ = xyz, ‘STR2’ = abcd

Output: 1
In this case, ‘STR1[0]>STR2[0]’ hence ‘STR1’ is better than ‘STR2’. Hence the output will be ‘1’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', the number of test cases.

Each test case consists of two lines.

The first line of input contains two integers, ‘N’ and ‘M’ separated by spaces.

Followed by two lines containing strings ‘STR1’ of length ‘N’ and ‘STR2’ of length ‘M’.
Output format : 
For each test case, print ‘1’ or ‘0’ or ‘-1’ depending on the relation between ‘STR1’ and ‘STR2’.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
1 <= ‘M’ <= 10^5
‘STR1’ and ‘STR2’ consists of lowercase letters.
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
It is guaranteed that sum of ‘M’ over all test cases is <= 10^5
Time Limit: 1 sec
Sample Input 1 :
2
1 3
a
abc
3 3
abz
abc
Sample Output 1 :
-1
1
Explanation Of Sample Input 1 :
For the first test case, ‘STR2’ is better than ‘STR1’, as they are the same until the ‘0th’ index and then string ‘STR1’ ends and as explained in the statement for ‘M>N’, the answer is ‘-1’.

Hence, the output will be: -1

For the second test case, ‘STR1’ is better than ‘STR2’, as they are the same until the ‘1st’ index and then ‘STR1[2]>STR2[2]’.

Hence, the output will be: 1
Sample Input 2 :
3
2 3
ez
ehz
5 5
acefi
acefi
3 5
ags
agtaa
Sample Output 2 :
1
0
-1
Hint

Can we iterate on the given strings in some order?.

Approaches (1)
Simulation

The idea for this approach is to iterate on the given string ‘STR1’ and ‘STR2’ with the same pointer and check if the elements at some index are not equal then we return the appropriate answer. And if it remains the same we keep comparing it until the pointer goes out of bound for any one of the strings.
 

If it goes out of bound for both strings we return ‘0’, else if it exceeds ‘N’ we return ‘-1’, or if it exceeds ‘M’ we return ‘1’.
 

Algorithm:
 

// The function will return the relation between ‘STR1’ and ‘STR2’.

Int stringMania(N, M, STR1, STR2)

  • Initialize a variable named ‘ANS’ with the value of ‘-2’.
  • Run a for loop from ‘0’ to ‘min(N, M) - 1’ with a variable named ‘i’.
    • If ‘STR1[i] == STR2[i]’
      • Skip this iteration.
    • If ‘STR1[i]>STR2[i]’
      • Assign ‘ANS’ the value of ‘1’.
    • If ‘STR2[i]>STR1[i]’
      • Assign ‘ANS’ the value of ‘-1’
    • Stop the loop.
  • If ‘ANS == -2’
    • If ‘N == M’
      • Assign ‘ANS’ the value of ‘0’.
    • Else
      • Assign ‘ANS’ the value of ‘(N-M)/abs(N-M)’.
  • Return ‘ANS’.
Time Complexity

O(min(N, M)), Where ‘N’ and ‘M’ are input integers.

As we iterate on the given string ‘STR1’ and ‘STR2’ until one of the strings ends i.e. ‘min(N, M)’ iterations, the time complexity will be O(min(N, M)).

Space Complexity

O(1),

 

As we just use ‘ANS’ and some temporary loop variables, the space complexity will be O(1).

Code Solution
(100% EXP penalty)
String Mania
Full screen
Console