Easy

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

这道题要求找到两个相同字符之间的最长子字符串长度。有两种主要思路：

方法一：暴力枚举 对每个位置的字符，向右查找是否存在相同字符，计算它们之间的距离。时间复杂度为 O(n²)。

方法二：哈希表记录位置（推荐） 使用哈希表记录每个字符的第一次出现位置。遍历字符串时，如果当前字符之前出现过，就计算两个位置之间的距离。这种方法只需要一次遍历，时间复杂度为 O(n)。

具体步骤：

  1. 创建哈希表存储每个字符的首次出现位置
  2. 遍历字符串，对于每个字符：
    • 如果字符已在哈希表中，计算当前位置与首次位置的距离减1
    • 更新最大长度
    • 如果字符不在哈希表中，记录其首次位置
  3. 返回最大长度，如果没有找到相同字符则返回-1

这种方法充分利用了哈希表O(1)的查找特性，是最优解法。

代码实现

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        unordered_map<char, int> firstPos;
        int maxLen = -1;
        
        for (int i = 0; i < s.length(); i++) {
            if (firstPos.find(s[i]) != firstPos.end()) {
                maxLen = max(maxLen, i - firstPos[s[i]] - 1);
            } else {
                firstPos[s[i]] = i;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        first_pos = {}
        max_len = -1
        
        for i, char in enumerate(s):
            if char in first_pos:
                max_len = max(max_len, i - first_pos[char] - 1)
            else:
                first_pos[char] = i
        
        return max_len

public class Solution {
    public int MaxLengthBetweenEqualCharacters(string s) {
        Dictionary<char, int> firstPos = new Dictionary<char, int>();
        int maxLen = -1;
        
        for (int i = 0; i < s.Length; i++) {
            if (firstPos.ContainsKey(s[i])) {
                maxLen = Math.Max(maxLen, i - firstPos[s[i]] - 1);
            } else {
                firstPos[s[i]] = i;
            }
        }
        
        return maxLen;
    }
}

var maxLengthBetweenEqualCharacters = function(s) {
    const firstPos = new Map();
    let maxLen = -1;
    
    for (let i = 0; i < s.length; i++) {
        if (firstPos.has(s[i])) {
            maxLen = Math.max(maxLen, i - firstPos.get(s[i]) - 1);
        } else {
            firstPos.set(s[i], i);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历字符串一次，哈希表操作为O(1)
空间复杂度O(1)最多存储26个小写字母，常数级空间