简单

问题描述

给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：s = "aa"
输出：0
解释：最优的子字符串是两个 'a' 之间的空子字符串。

示例 2：

输入：s = "abca"
输出：2
解释：最优的子字符串是 "bc" 。

示例 3：

输入：s = "cbzxy"
输出：-1
解释：s 中不存在出现出现两次的字符，所以返回 -1 。

示例 4：

输入：s = "cabbac"
输出：4
解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。

提示：

• 1 <= s.length <= 300
• s 只含小写英文字母

一次遍历

字符串只包含小写字母，因此创建一个长度为 $26$ 的数组，遍历字符串，记录每个字母首次出现的位置，若遇到非首次出现的字母时，计算与首次出现的位置的距离并记录最大值，最后返回记录到的最大值即可。

/**
 * @param {string} s
 * @return {number}
 */
var maxLengthBetweenEqualCharacters = function (s) {
  const arr = new Array(26).fill(-1)
  let ans = -1
  for (let i = 0; i < s.length; i++) {
    const n = s.charCodeAt(i) - 97
    if (arr[n] === -1) {
      arr[n] = i
    } else {
      ans = Math.max(ans, i - arr[n] - 1)
    }
  }
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(C)$，其中 $C=26$ 为字符集大小