1624. 两个相同字符之间的最长子字符串

🟢   🔖  哈希表 字符串  🔗 力扣 LeetCode

题目

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aa"

Output: 0

Explanation: The optimal substring here is an empty substring between the two 'a's.

Example 2:

Input: s = "abca"

Output: 2

Explanation: The optimal substring here is "bc".

Example 3:

Input: s = "cbzxy"

Output: -1

Explanation: There are no characters that appear twice in s.

Constraints:

• 1 <= s.length <= 300
• s contains only lowercase English letters.

题目大意

给你一个字符串 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 只含小写英文字母

解题思路

1. 定义状态存储第一个出现位置：

   • 使用一个长度为 26 的数组 firstIndex 来记录每个字符的首次出现索引。
   • 初始化数组的所有值为 n，即数组长度，这表示该字符尚未出现在字符串中。
   • 定义变量 longest 来记录两个相同字符之间的最长子字符串的长度，初始化为 -1，即无符合条件的字符；

2. 遍历字符串：

   • 对于每个字符 s[i]：
     • 计算其在 firstIndex 中对应的索引 code，公式为： s[i].charCodeAt() - 97
     • 如果 firstIndex[code] 为初始值 n，说明这是该字符的首次出现，记录其索引： firstIndex[code] = i
     • 否则，该字符已出现过，计算当前索引和首次索引的间隔长度，并尝试更新最长间隔： longest = Math.max(longest, i - firstIndex[code] - 1)

3. 最后返回 longest。

复杂度分析

• 时间复杂度：O(n)，只需遍历字符串一次，每次操作为常数时间。

• 空间复杂度：O(1)，使用了固定大小的数组 firstIndex，大小为 26。

代码

/**
 * @param {string} s
 * @return {number}
 */
var maxLengthBetweenEqualCharacters = function (s) {
	const n = s.length;
	let firstIndex = new Array(26).fill(n); // 初始化为 n，表示字符尚未出现
	let longest = -1; // 初始化为 -1，表示尚未找到符合条件的字符

	for (let i = 0; i < n; i++) {
		const code = s[i].charCodeAt() - 97; // 计算字符的数组索引
		if (firstIndex[code] === n) {
			// 首次出现
			firstIndex[code] = i;
		} else {
			// 已出现过，计算间隔并更新最长距离
			longest = Math.max(longest, i - firstIndex[code] - 1);
		}
	}
	return longest;
};