给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
示例代码
- (NSInteger)hy_lengthOfLongestSubstring:(NSString *)s {
if (s.length == 0) {
return 0;
}
NSInteger maxLength = 0;
NSInteger left = 0, right = 0;
NSMutableDictionary *charDict = [NSMutableDictionary dictionary];
while (right < s.length) {
NSString *currentChar = [s substringWithRange:NSMakeRange(right, 1)];
if ([charDict objectForKey:currentChar]) {
NSNumber *prevIndex = [charDict objectForKey:currentChar];
left = MAX(left, prevIndex.integerValue + 1);
}
[charDict setObject:@(right) forKey:currentChar];
maxLength = MAX(maxLength, right - left + 1);
right++;
}
return maxLength;
}
这个算法的基本思想是使用滑动窗口来维护最长不重复子串。我们使用两个指针 left 和 right 来表示当前窗口的左右边界。我们还使用一个字典来存储每个字符在字符串中出现的最后位置(即上一次出现的位置)。
当我们移动 right 指针时,我们检查当前字符是否已经在窗口中出现。如果是,则更新 left 指针以跳过前面的所有重复字符,并且将当前字符的位置添加到字典中。同时,我们还需要更新最长不重复子串的长度。
要找到字符串中的最长不重复子串长度,只需调用 lengthOfLongestSubstring 方法,并将要计算的字符串作为参数传递给它即可。