2981。找到出現(xiàn)三次的最長(zhǎng)特殊子串 I

難度：中等

主題：哈希表、字符串、二分查找、滑動(dòng)窗口、計(jì)數(shù)

給你一個(gè)由小寫英文字母組成的字符串 s。

如果字符串僅由單個(gè)字符組成，則稱為特殊。例如，字符串“abc”并不特殊，而字符串“ddd”、“zz”和“f”則特殊。

返回s中出現(xiàn)至少三次的最長(zhǎng)特殊子串的長(zhǎng)度，如果沒有特殊子串至少出現(xiàn)三次，則返回-1。

子字符串是字符串中連續(xù)的非空字符序列。

示例1：

• 輸入： s = "aaaa"
• 輸出： 2
• 解釋： 出現(xiàn)三次的最長(zhǎng)特殊子串是“aa”：子串“aaaa”、“aaaa”和“aaaa”。
  • 可以證明，可實(shí)現(xiàn)的最大長(zhǎng)度為2。

示例2：

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

示例 3：

• 輸入： s = "abcdef"
• 輸出： 1
• 解釋： 出現(xiàn)三次的最長(zhǎng)特殊子串是“a”：子串“abcaba”、“abcaba”和“abcaba”。
  • 可以證明，可達(dá)到的最大長(zhǎng)度為1。

約束：

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

提示：

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

解決方案：

由于 s 的限制較?。ㄩL(zhǎng)度最多為 50），我們可以使用強(qiáng)力方法。我們會(huì)：

1. 迭代子字符串的可能長(zhǎng)度（從最長(zhǎng)到最短）。
2. 檢查給定長(zhǎng)度的所有子字符串并計(jì)算它們的出現(xiàn)次數(shù)。
3. 如果某個(gè)子字符串至少出現(xiàn) 3 次，請(qǐng)檢查它是否特殊（由一個(gè)重復(fù)字符組成）。
4. 返回最長(zhǎng)的子字符串的長(zhǎng)度。如果沒有子串滿足條件，則返回-1。

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：2981。查找出現(xiàn)三次的最長(zhǎng)特殊子串 I

<?php
/**
 * @param String $s
 * @return Integer
 */
function maximumLength($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a substring is special
 *
 * @param $substring
 * @return bool
 */
function isSpecial($substring) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maximumLength("aaaa") . "\n"; // Output: 2
echo maximumLength("abcdef") . "\n"; // Output: -1
echo maximumLength("abcabcabc") . "\n"; // Output: 1
?>

解釋：

1. 外循環(huán)：我們從最長(zhǎng)的開始迭代子字符串的可能長(zhǎng)度。這確保我們?cè)谡业阶铋L(zhǎng)的特殊子字符串后立即返回它。
2. 滑動(dòng)窗口：對(duì)于每個(gè)子字符串長(zhǎng)度，我們使用滑動(dòng)窗口方法來提取該長(zhǎng)度的所有子字符串。
3. 計(jì)算子字符串：我們使用關(guān)聯(lián)數(shù)組（$countMap）來存儲(chǔ)和計(jì)算每個(gè)子字符串的出現(xiàn)次數(shù)。
4. 檢查特殊：輔助函數(shù) isSpecial 檢查子字符串是否僅由一個(gè)重復(fù)字符組成。
5. 返回結(jié)果：如果找到有效的子字符串，我們返回它的長(zhǎng)度；否則，我們返回 -1。

復(fù)雜

• 時(shí)間復(fù)雜度：在最壞的情況下O(n³)，因?yàn)槲覀儯?
  1. 迭代 n 個(gè)子字符串長(zhǎng)度。
  2. 為每個(gè)長(zhǎng)度提取 O(n) 個(gè)子串。
  3. 檢查每個(gè)子串是否特殊，需要O(n)時(shí)間。
• 空間復(fù)雜度: O(n²) 由于子串計(jì)數(shù)映射。

考慮到約束條件，這種強(qiáng)力方法是可行的 (n )。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫(kù) 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對(duì)我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是找到出現(xiàn)三次的最長(zhǎng)特殊子串 I的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！