找到出现三次的最长特殊子串 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

<?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. 外循环：我们从最长的开始迭代子字符串的可能长度。这确保我们在找到最长的特殊子字符串后立即返回它。
2. 滑动窗口：对于每个子字符串长度，我们使用滑动窗口方法来提取该长度的所有子字符串。
3. 计算子字符串：我们使用关联数组（$countMap）来存储和计算每个子字符串的出现次数。
4. 检查特殊：辅助函数 isSpecial 检查子字符串是否仅由一个重复字符组成。
5. 返回结果：如果找到有效的子字符串，我们返回它的长度；否则，我们返回 -1。

复杂

• 时间复杂度：在最坏的情况下O(n³)，因为我们：
  1. 迭代 n 个子字符串长度。
  2. 为每个长度提取 O(n) 个子串。
  3. 检查每个子串是否特殊，需要O(n)时间。
• 空间复杂度: O(n²) 由于子串计数映射。

考虑到约束条件，这种强力方法是可行的 (n )。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是找到出现三次的最长特殊子串 I的详细内容。更多信息请关注PHP中文网其他相关文章！