最大比例的子串

Question

我們假設我有一些包含{A,B}的序列，每個字母在一個序列中至少有一個出現。如何找到符合要求的序列中的子：

• 的數A對B的數量應該是儘可能高的比例（＃A /＃乙 - >最大）
• 如果有很多子用相同的比例我們不得不返回最長的子
• 最後，如果有很多人有相同的長度，我們不得不回到較低的起始索引

作爲輸出的一個我們要找到字符串的開始，它的長度指數。

例

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

任何提示如何處理的問題？

爲請求我加入了我的想法：

1. 如果連續A的一些兩組有3個或更多B的，沒有理由進一步測試它分開。這很簡單，因爲如果我們像串：...A{k}BBBA{m}...比(k+m):3而k:1或m:1必須給予更好的選擇

2. 我試着也發現A的所有子最長的順序。我認爲這將是非常propable我的順序會是這樣的A{N1}BA{N2}BA{N3}但後來我發現它不necesearily例如真：

   BABAABBAAA

我們可以看到有兩個序列具有相同的比例：

1. I = 1個長度= 4
2. I = 6長度= 4

但由於規則3意味着我應該返回第一個wheres，因爲我說我的算法是基於最長的連續A的順序。

Answer 1

這看起來像一個家庭作業，所以這可能不是一個很好的回答問題。然而，提示是以簡單情況開始的：

1. 如果在序列中只有一個B會發生什麼？
2. 如果有兩個B會怎麼樣？假設你的序列中包含x A的，那麼單個B，然後y A的，再單個B，然後z A的寫一些不等式。
3. 對所有序列進行推理（提示：對於任何數字序列a[1] ... a[n](a[1] + ... + a[n])/n <= max(a[1], ... , a[n]，並且只有當所有元素都相等時纔會出現相等）。