Last Updated: 8 Jul, 2022

String Mania

Easy

Solve now

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’.

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

Solve now

Approaches

01 Approach

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’.

Solve now