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

这道题拿到手想法就是去双重遍历暴力解，对于每个字符，从后往前遍历字符串，找到从后往前一直到本次遍历的这个字符串这段子串中和这个字符串相同的字符位置，然后得到子字符串的长度，和ans存储的值做一个比较，如果比ans值大就更新，小就舍弃。时间复杂度

O

(

n

2

)

O(n^2)

O(n2)

class Solution(object):
    def maxLengthBetweenEqualCharacters(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans = -1
        for i in range(len(s)):
            for j in range(len(s) - 1, -1, -1):
                if s[i] == s[j] and i <= j:
                    ans = j - i - 1 if j - i - 1 > ans else ans
        return ans

题解的方法更为巧妙，对于字符ch，只需要求出ch第一次出现在字符串中的索引位置first 和最后一次出现在字符串中的索引位置last，则以ch为相同字符之间的子字符串的最大长度一定为last−first−1，我们依次求出所有可能的子字符的长度的最大值即可。设数组firstIndex记录每个字符i在字符串中第一次出现的索引，maxLength表示当前子字符串的最大长度。
首先我们开辟一个长度为26的数组，初始值都是-1，表示该字符还未出现过，然后开始遍历整个字符串，当遇到一个字符时，判断其是否出现过，也就是其值是否为-1，如果是，证明是第一次出现，更新其值为其对应索引firstIndex[c] = i即可，如果其值不是-1，则证明这个数字已经出现过了，则计算i – firstIndex[c] – 1，同时和ans比较，若大则更新ans即可。时间复杂度

O

(

n

)

O(n)

O(n)

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        ans = -1
        firstIndex = {}
        for i, c in enumerate(s):  # enumerate 函数用于同时获取一个可迭代对象的索引和值
            if c not in firstIndex:
                firstIndex[c] = i
            else:
                ans = max(ans, i - firstIndex[c] - 1)
        return ans