3 Longest Substring Without Repeating Characters

Medium

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

Example 1:

1
2
3

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

Example 2:

1
2
3

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.

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

想法

这道题一方面可以直接用双指针去遍历，复杂度基本为$O(n)$，另一方面可以用一个Trick：通过记录字符最后出现的位置，当出现重复字符的时候将左指针直接跳转至重复字符最后出现的位置而非不断+1，这样虽然复杂度不变，但是计算次数变少。

解

class Solution {
  public:
    int lengthOfLongestSubstring(string s)
    {
        int index[300];
        memset(index, 0, sizeof(int) * 300);
        int ans = 0;
        for (int i = 0, j = 0; j < s.size(); j++) {
            i = max(i, index[s[j]]);
            ans = max(ans, j - i + 1);
            index[s[j]] = j + 1;
        }
        return ans;
    }
};

2018-08-15

在Ubuntu Server上配置CUDA环境

Basic

3 Longest Substring Without Repeating Characters

想法

解

喜欢这篇文章？打赏一下作者吧

评论

链接

标签云

最新文章

归档

分类

标签

Your browser is out-of-date!