两个相同字符之间的最长子字符串
难度:
标签:
题目描述
代码结果
运行时间: 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,尤其是在考虑字符串中可能出现的重复字符的情况下?
▷🦆
这种方法在处理字符全部不同的情况下的返回值是如何确定的,为什么能确保正确?
▷