找出出現三次的最長特殊子字串 I

2981。找出出現三次的最長特殊子字串 I

難度：中

主題：雜湊表、字串、二分查找、滑動視窗、計數

給你一個由小寫英文字母組成的字串 s。

如果字串僅由單字組成，則稱為特殊。例如，字串「abc」並不特殊，而字串「ddd」、「zz」和「f」則是特殊。

回傳s中出現至少三次的最長特殊子字串的長度，如果沒有特殊子字串至少出現三次，則回傳-1。

子字串是字串中連續的非空字元序列。

範例1：

• 輸入： s = "aaaa"
• 輸出： 2
• 解釋： 出現三次的最長特殊子字串是「aa」：子字串「aaaa」、「aaaa」和「aaaa」。
  • 可以證明，可實現的最大長度為2。

範例2：

• 輸入： s = "abcdef"
• 輸出： -1
• 解釋：不存在至少出現三次的特殊子字串。因此返回-1。

範例 3：

• 輸入： s = "abcdef"
• 輸出： 1
• 解釋： 出現三次的最長特殊子字串是「a」：子字串「abcaba」、「abcaba」和「abcaba」。
  • 可以證明，可達到的最大長度為1。

約束：

• 3
• s 僅由小寫英文字母組成。

提示：

1. 限制很小。
2. 暴力檢查所有子字串。

解：

由於 s 的限制較小（長度最多為 50），我們可以使用強力方法。我們會：

1. 迭代子字串的可能長度（從最長到最短）。
2. 檢查給定長度的所有子字串併計算它們的出現次數。
3. 如果某個子字串至少出現 3 次，請檢查它是否特殊（由一個重複字元組成）。
4. 傳回最長的子字串的長度。如果沒有子字串滿足條件，則傳回-1。

讓我們用 PHP 實作這個解：2981。找出出現三次的最長特殊子字串 I

解釋：

1. 外循環：我們從最長的開始迭代子字串的可能長度。這確保我們在找到最長的特殊子字串後立即返回它。
2. 滑動視窗：對於每個子字串長度，我們使用滑動視窗方法來提取該長度的所有子字串。
3. 計算子字串：我們使用關聯數組（$countMap）來儲存和計算每個子字串的出現次數。
4. 檢查特殊：輔助函數 isSpecial 檢查子字串是否僅由一個重複字元組成。
5. 傳回結果：如果找到有效的子字串，我們傳回它的長度；否則，我們傳回 -1。

複雜

• 時間複雜度：在最壞的情況下O(n³)，因為我們：
  1. 迭代 n 個子字串長度。
  2. 為每個長度提取 O(n) 個子字串。
  3. 檢查每個子字串是否特殊，需要O(n)時間。
• 空間複雜度: O(n²) 由於子字串計數對應。

考慮到限制條件，這種強力方法是可行的 (n )。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是找出出現三次的最長特殊子字串 I的詳細內容。更多資訊請關注PHP中文網其他相關文章！