title: Google Interview : Find Crazy Distance Between Strings
body: <p>This Question was asked to me at the Google interview. I could do it O(n*n) ... Can I do it in  better time. 
  A string can be formed only by 1 and 0. </p>
  
  <p>Definition:</p>
  
  <p>X &amp; Y are strings formed by 0 or 1</p>
  
  <p><code>D(X,Y)</code> = Remove the things common at the start from both X &amp; Y. Then add the remaining lengths from both the strings. </p>
  
  <p>For e.g.</p>
  
  <p><code>D(1111, 1000)</code> = Only First alphabet is common. So the remaining string is <code>111</code> &amp; <code>000</code>. Therefore the result <code>length("111")</code> &amp; <code>length("000")</code> = 3 + 3 = 6</p>
  
  <p><code>D(101, 1100)</code> = Only First two alphabets are common. So the remaining string is <code>01</code> &amp; <code>100</code>. Therefore the result <code>length("01")</code> &amp; <code>length("100")</code> = 2 + 3 = 5</p>
  
  <p>It is pretty that obvious that do find out such a crazy distance is going to be linear. O(m).</p>
  
  <p>Now the question is </p>
  
  <p>given n input, say like</p>
  
  <pre><code>1111
  1000
  101
  1100
  </code></pre>
  
  <p>Find out the maximum crazy distance possible. </p>
  
  <p>n is the number of input strings.
  m is the max length of any input string.</p>
  
  <p>The solution of O(n<sup>2</sup> * m) is pretty simple. Can it be done in a better way?
  Let's assume that m is fixed. Can we do this in better than O(n^2) ? </p>