title: Substring with greatest ratio
body: <p>Let's assume I have some sequence containing <code>{A,B}</code> and there is at least one occurrence of each letter in a sequence. How to find substring within sequence that fulfill requirements:</p>
  
  <ul>
  <li>number of A's to number of B's should be highest possible ratio (#A/#B --> max)</li>
  <li>if there are many substring with same ratio we have to return longest possible substring</li>
  <li>finally if there are many of them with same length, we had to return the one with lower beginning index </li>
  </ul>
  
  <p>As output we want index of beginning of found substring and it's length.</p>
  
  <p>Example</p>
  
  <pre><code>IN: AAABAA
  OUT: index = 0, length = 6 (ratio is 5 : 1)
  IN: BABAABBA
  OUT: index = 1, length = 4 (ratio is 3 : 1)
  </code></pre>
  
  <p>Any hints how to approach problem?</p>
  
  <p>As a request I'm adding my thoughts:</p>
  
  <ol>
  <li>If some two groups of consecutive A's are separated with 3 or more B's there's no reason to test it further. It's quite simple because if we had substring like: <code>...A{k}BBBA{m}...</code> ratio is <code>(k+m):3</code> whereas <code>k:1</code> or <code>m:1</code> must give better option</li>
  <li><p>I tried also finding all longest substrings of A's in sequence. I thought it would be highly propable that my sequence would be something like <code>A{N1}BA{N2}BA{N3}</code> but later on I found it not necesearily true for instance:</p>
  
  <p>BABAABBAAA</p></li>
  </ol>
  
  <p>As we can see there are two sequence with same ratio:</p>
  
  <ol>
  <li>i=1 length=4</li>
  <li>i=6 length=4</li>
  </ol>
  
  <p>But as rule 3rd implies I should return the first one wheres as I said my algorithm was based on longest consecutive A's in sequence.</p>