Maximum Distance

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

In this approach, we will maintain a trie and at each node of the trie. We will iterate over all strings and their characters, and for each character, we will store the distance from the end of the string. If the character is ‘0’, we will add the node to the left side, and if the character is ‘1’, we will add it to the right side.

Then we traverse the trie, and at each node, if there are branching nodes, then there is a different string up to with the same prefix up to that node. Then will add the check the distances of their nodes from the end of their respective strings.

We create TrieNode(val) class with left and right pointers, val integer, and isEnd boolean.

We create a function buildTrie(s, root) where s is the strings array and root the root node of the trie.

Algorithm:

• In the function buildTrie(s, root)
  • Iterate currString through arr
    • Set currNode as root
    • Iterate i from 0 to length of currString -1
      • Set distance as the length of currString - i
      • If currString[i] is equal to ‘0’
        • If currNode.left is null
          • Set currNode.left as TrieNode(distance)
        • Otherwise,
          • Set currNode.left.val as maximum of distance and currNode.left.val
      • Otherwise,
        • If currNode.right is null
          • Set currNode.right as TrieNode(distance)
        • Otherwise,
          • Set currNode.right.val as maximum of distance and currNode.right.val
      • Set currNode.isEnd as True

• Set root as TrieNode(0)
• Call buildTrie(root, s)
• Set maxDistance as 0
• Initialise an queue q
• Insert root in q
• While q is not empty
  • Set currNode as the front of the queue
  • Remove the front of the queue
  • If either currNode.left or currNode.right is not equal to null
    • If currNode.left and currNode.right both are not null
      • Set maxDistance as maximum of maxDistance and the sum of  currNode.left.val currNode.right.val
    • If currNode.isEnd is True
    • Set maxDistance as the maximum of maxDistance, and if currNode.left is not null then currNode.left otherwise currNode.right
  • If currNode.left is not null
    • Insert currNode.left in q
  • If currNode.right is not null
    • Insert currNode.right in q
• Finally return maxDistance.