Maximum Distance

Hard
0/120
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in companies
Expedia GroupGoogle inc

Problem statement

You are given an array of binary strings ‘arr’ of size ‘N’. Your task is to find out the maximum distance between the pair of strings.

The distance between two binary strings is defined as the sum of their lengths after removing the common prefix.

For example: 
You are given ‘arr’ = [ “01011”,  “010110”, “0111”], Here the strings with the maximum distance between them are “010110” and  “0111”, where the prefix is “01”,  hence the maximum distance is  4 + 2 = 6. Hence the answer is 6.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
 The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains ‘N’ space-separated strings representing the elements of the array ‘arr’.
Output Format: 
For each test case, print a single integer representing the maximum distance between any two strings in the array.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
2 <= N <= 10^3
1 <= |arr[i]| <= 10^3

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
1011100 1011011 1001111 0111111
01011 010110 0111
Sample Output 1:
14
 6
Explanation:
For the first test case, ‘arr’ = ["1011100", "1011011", "1001111", "0111111"], Here the string with maximum distance between them are "1001111" and  "0111111”, where the prefix is “”,  hence the maximum distance is 7 + 7 = 14. Hence the answer is 14.

For the second test case, ‘arr’ = [ “01011”,  “010110”, “0111”], Here the strings with the maximum distance between them are “010110” and  “0111”, where the prefix is “01”. Hence the maximum distance is  4 + 2 = 6. Hence the answer is 6.
Sample Input 2:
2
1100 1110 0111 00
01000 01011 010 011
Sample Output 2:
8
4
Hint

Try to think of a brute force approach.

Approaches (2)
Brute Force

In this approach, we will check all the possible pairs of strings calculate the maximum distance between all the possible pairs. For each pair, we will traverse from the beginning of each string until they match, then we will remove the matching prefix and add the remaining lengths of the string.
 

We create a function calculateDistance(firstString, secondString) to get the distance between each pair of strings where firstString and secondString are the strings.

 

Algorithm:

  • If the function calculateDistance(firstString, secondString)
    • Set i and j equal to 0
    • While i is less than size of firstString and j is less than size of secondString
      • If firstString[i] is not equal to secondString[j] then,
        • Break the loop
      • Increase both i and j by 1
    • Return  the sum of the length of firstString - i and the length of secondString - j
  • Set maxDistance as 0
  • Iterate firstString thourgh arr
    • Iterate secondString through arr
      • Set maxDistance as the maximum of maxDistance and calculateDistance(firstString, secondString)
  • Finally, return maxDistance
Time Complexity

O((N^2)*M), Where N is the number of strings and M is the average length of each string.

 

We are iterating the whole array for each string in the array that will take O(N^2) time, and for each pair of strings, we calculate the distance between them, which will take O(M) time. Hence the overall time complexity is O((N^2)*M).

Space Complexity

O(1).

 

We are not using any extra space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Maximum Distance
Full screen
Console