首页 > 其他 > 详细

3. Longest Substring Without Repeating Characters - Medium - Leetcode解题报告

时间:2019-05-21 00:49:22      阅读:116      评论:0      收藏:0      [点我收藏+]

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Related Topic: Hash Table, Two Pointers, String, Sliding Window

解题思路:用Sliding Window法,维护头尾两个指针构成合法的结果区间,即保证start与end之间为无重复字符的子串。利用HashMap记录每个字符出现在字符串中的最后位置,end从起始点一直向后扫,若当前字符curr已出现在HashMap中,且curr在HashMap中所保存的index(该字符在前面最后一次出现的位置)大于等于start点,则当前的(start,end)区间已出现两次curr字符,不再合法,将start重置为map.get(curr) + 1, 因为截止到map.get(curr)已经不再合法了。循环遍历时更新当前字符curr在字符串中所出现的最后位置,记录在map中。在循环遍历的最后面计算当前合法的最大子串长度,持续更新。

Time Complexity: O(n), Space Complexity: O(n)

Java version:

 1 class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         if (s == null || s.length() == 0) {
 4             return 0;
 5         }
 6         
 7         Map<Character, Integer> map = new HashMap<>();
 8         int max = 0;
 9         int start = 0;
10         
11         for (int end = 0; end < s.length(); end++) {
12             char curr = s.charAt(end);
13             if (map.containsKey(curr) && map.get(curr) >= start) {
14                 start = map.get(curr) + 1;
15             }
16             map.put(curr, end);
17             max = Math.max(max, end - start + 1);
18         }
19         
20         return max;
21     }
22 }

JavaScript version:

 1 /**
 2  * @param {string} s
 3  * @return {number}
 4  */
 5 var lengthOfLongestSubstring = function(s) {
 6     if (s == null || s.length == 0) {
 7         return 0;
 8     }
 9     
10     var map = new Map();
11     var max = 0;
12     var start = 0;
13     
14     for (var end = 0; end < s.length; end++) {
15         var curr = s.charAt(end);
16         if (map.has(curr) && map.get(curr) >= start) {
17             start = map.get(curr) + 1;
18         }
19         map.set(curr, end);
20         max = Math.max(max, end - start + 1);
21     }
22     
23     return max;
24 };

Python version:

 1 class Solution:
 2     def lengthOfLongestSubstring(self, s: str) -> int:
 3         if len(s) == 0:
 4             return 0
 5         
 6         dict = {}
 7         start = 0
 8         max_list = [None] * len(s)
 9         
10         for end in range(len(s)):
11             curr = s[end]
12             if dict.get(curr) is not None and dict[curr] >= start:
13                 start = dict[curr] + 1
14             
15             dict[curr] = end
16             max_list[end] = end - start + 1
17         
18         return max(max_list)

 

3. Longest Substring Without Repeating Characters - Medium - Leetcode解题报告

原文:https://www.cnblogs.com/raymondwang/p/10897508.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!