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

题目描述

这是 LeetCode 上的 1624. 两个相同字符之间的最长子字符串 ，难度为 简单。

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

---

模拟

根据题意继续模拟即可：使用数组 idxs 记录下每个字符最开始出现的下标即可。

Java 代码：

class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        int[] idxs = new int[26];
        Arrays.fill(idxs, 310);
        int n = s.length(), ans = -1;
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            idxs[u] = Math.min(idxs[u], i);
            ans = Math.max(ans, i - idxs[u] - 1);
        }
        return ans;
    }
}

Typescript 代码：

function maxLengthBetweenEqualCharacters(s: string): number {
    const idxs = new Array<number>(26).fill(310)
    let n = s.length, ans = -1
    for (let i = 0; i < n; i++) {
        const u = s.charCodeAt(i) - 'a'.charCodeAt(0)
        idxs[u] = Math.min(idxs[u], i)
        ans = Math.max(ans, i - idxs[u] - 1)
    }
    return ans
};

Python 代码：

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

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

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1624 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。