leetcode
leetcode 1451 ~ 1500
两个相同字符之间的最长子字符串

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

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 15.9 MB


/*
 * 题目思路:
 * 使用Java Stream API来解决这个问题。
 * 首先创建一个包含字符及其索引的流。
 * 然后将相同字符的索引进行分组,并计算最大长度。
 */
import java.util.stream.IntStream;
import java.util.stream.Collectors;
import java.util.Map;

public class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        Map<Character, int[]> map = IntStream.range(0, s.length())
                .boxed()
                .collect(Collectors.toMap(i -> s.charAt(i), i -> new int[]{i, i}, (a, b) -> new int[]{a[0], b[1]}));
        return map.values().stream()
                .mapToInt(pair -> pair[1] - pair[0] - 1)
                .max()
                .orElse(-1);
    }
}

解释

方法:

此题解的思路基于字典来记录每个字符首次出现的位置。遍历字符串中的每个字符,如果字符是首次出现,则在字典中记录该字符和它的索引。如果字符已经在字典中,说明之前已经遇到过一次,此时计算当前位置与首次出现位置之间的字符数(即两个相同字符之间的最长子字符串的长度),并更新最大长度。最后返回记录的最大长度。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在解题思路中,字典存储字符首次出现的索引,但如果字符多次出现怎样处理?是否需要更新该字符的索引或保持首次索引不变?
在这个算法中,字典存储的是每个字符首次出现的索引,并且这个索引在后续的遍历中不会被更新。这是因为我们的目标是找到两个相同字符之间的最长子字符串,这涉及到计算从首次出现位置到当前位置之间的距离。如果我们更新了字符的索引,那么我们将丧失首次出现的位置信息,从而无法正确计算出两次出现之间的距离。因此,即使字符多次出现,我们也保持字典中该字符索引的值不变,始终指向该字符在字符串中首次出现的位置。
🦆
为什么在算法中初始化答案为-1,而不是0,尤其是在考虑字符串中可能出现的重复字符的情况下?
在这个算法中,答案初始化为-1是为了处理那些没有任何两个相同字符的字符串的情况。如果字符串中的所有字符都是唯一的,那么就不存在两个相同字符之间的子字符串,因此最长子字符串的长度应该是不存在的,即返回-1。如果初始化为0,在字符串中没有重复字符的情况下,返回0将错误地暗示存在长度为0的子字符串,这并不准确。因此,初始化为-1是为了在特殊情况下提供正确的返回值,并明确表示没有找到有效的子字符串。
🦆
这种方法在处理字符全部不同的情况下的返回值是如何确定的,为什么能确保正确?
当处理的字符串中的所有字符都是不同的,字典将记录每个字符的索引,但由于没有任何字符会重复出现,字典中的索引不会被用于计算任何子字符串的长度。因此,字典的存在仅用于记录首次出现的位置,而由于没有重复的字符触发长度计算的条件,初始化的答案-1将不会被任何计算所修改。这样,算法最终返回-1,确切地反映了这种情况下的正确结果:没有两个相同字符之间的子字符串。

相关问题