CODEWITHSUNDEEP
algorithmsubstring
abc
abc

Reputation: 2381

Substring with greatest ratio

Let's assume I have some sequence containing {A,B} and there is at least one occurrence of each letter in a sequence. How to find substring within sequence that fulfill requirements:

As output we want index of beginning of found substring and it's length.

Example

IN: AAABAA
OUT: index = 0, length = 6 (ratio is 5 : 1)
IN: BABAABBA
OUT: index = 1, length = 4 (ratio is 3 : 1)

Any hints how to approach problem?

As a request I'm adding my thoughts:

  1. 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: ...A{k}BBBA{m}... ratio is (k+m):3 whereas k:1 or m:1 must give better option

  2. 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 A{N1}BA{N2}BA{N3} but later on I found it not necesearily true for instance:

    BABAABBAAA

As we can see there are two sequence with same ratio:

  1. i=1 length=4
  2. i=6 length=4

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.

Upvotes: 0

Views: 131

Answers (1)

Wojciech Ptak
Wojciech Ptak

Reputation: 683

This looks like a homework, so that is probably not a good question to be answered fully. The hint, however, is to start with simple cases:

  1. What happens if you have only one B in the sequence?
  2. What happens if there are two B's? Assume your sequence contains x A's, then a single B, then y A's, then a single B again, and then z A's and write some inequalities.
  3. Make the reasoning work for all sequences (hint: for any sequence of numbers a[1] ... a[n] (a[1] + ... + a[n])/n <= max(a[1], ... , a[n], and the equality occurs only when all the element are equal).

Upvotes: 1

Related Questions