[leetcode] 1624. Largest Substring Between Two Equal Characters

[leetcode] 1624. Largest substring Between Two Equal Characters

Description

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: 0Explanation: The optimal substring here is an empty substring between the two 'a's.

Example 2:

Input: s = "abca"Output: 2Explanation: The optimal substring here is "bc".

Example 3:

Input: s = "cbzxy"Output: -1Explanation: There are no characters that appear twice in s.

Example 4:

Input: s = "cabbac"Output: 4Explanation: The optimal substring here is "abba". Other non-optimal substrings include "bb" and "".

Constraints:

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

分析

题目的意思是：移除两个相同字符串后剩下子串的最大长度，很显然分别移除位于最左的相同字符串就可以了。因此用一个字典保存字符串最左边的位置，当遍历到相同的字符串维护更新最大长度res就行了。

代码

class Solution: def maxLengthBetweenEqualCharacters(self, s: str) -> int: d={} res=-1 for i in range(len(s)): if(s[i] in d): res=max(res,i-d[s[i]]-1) else: d[s[i]]=i return res

参考文献

​​[LeetCode] 3 Solutions | Naive | Two Pass | One Pass O(n)​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。