leetcode-algorithms-3 Longest Substring Without Repeating Characters

时间:2023-01-27 20:24:20

leetcode-algorithms-3 Longest Substring Without Repeating Characters

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.

解法1

一步步检查所有字串看是否有重复的字符

class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
string longest;
for (int i = 0; i < s.size(); ++i)
{
for (int j = s.size() - i; j > 0; --j)
{
string longesttemp = s.substr(i, j); bool repect = false;
int a[256] = {0};
for (int n = 0; n < longesttemp.size(); ++n)
{
int x = longesttemp[n];
++a[x];
if (a[x] > 1)
{
repect = true;
break;
}
}
if (!repect && (longesttemp.size() > longest.size())) longest = longesttemp;
}
}
return longest.size();
}
};

时间复杂度: O(n^3).

空间复杂度: O(min(n,m)).

解法2

解法1的时间复杂度太高了,效率低下.字符串查找要怎么提高效率,首先都应该想到Sliding Window算法.设定一个窗口[i, j],将i到j的内容存入map,下面滑动j,如果s[j] (s表示字符串)在map中存在,表示字符串已经重复了,记下最大值,然后将i窗口滑到s[j]上次的位置.

下面是代码的实现:

class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int n = s.length();
std::unordered_map<char, int> m;
int len = 0; for (int i = 0, j = 0; j < n; ++j)
{
auto fiter = m.find(s[j]);
if (fiter != m.end())
{
i = (fiter->second) > i ? fiter->second : i;
} int temp_len = j - i + 1;
len = (len > temp_len) ? len : temp_len;
m[s[j]] = j + 1;
}
return len;
}
};

时间复杂度: O(n).只有一个j循环.

空间复杂度: O(m).m是最大的不重复子串的长度.

解法3

对于解法2有没更快捷的方式.参考KMP算法对字符串的处理,我们可以将字符存入整型数组,值存储字符所在的位置,这样就可以在算法2的基础上少一次查询.

class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int n = s.length();
int len = 0;
int index[128] = {0}; for (int i = 0, j = 0; j < n; ++j)
{
i = i > index[s[j]] ? i : index[s[j]];
int temp_len = j - i + 1;
len = (len > temp_len) ? len : temp_len;
index[s[j]] = j + 1;
}
return len;
}
};

时间复杂度: O(n).

空间复杂度: O(128).

链接: leetcode-algorithms 目录

leetcode-algorithms-3 Longest Substring Without Repeating Characters的更多相关文章

  1. 【一天一道LeetCode】 &num;3 Longest Substring Without Repeating Characters

    一天一道LeetCode (一)题目 Given a string, find the length of the longest substring without repeating charac ...

  2. 【LeetCode OJ】Longest Substring Without Repeating Characters

    题目链接:https://leetcode.com/problems/longest-substring-without-repeating-characters/ 题目:Given a string ...

  3. 【LeetCode】3&period; Longest Substring Without Repeating Characters 无重复字符的最长子串

    作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 公众号:负雪明烛 本文关键词:无重复字符,最长子串,题解,leetcode, 力扣,py ...

  4. 【LeetCode】3&period;Longest Substring Without Repeating Characters 最长无重复子串

    题目: Given a string, find the length of the longest substring without repeating characters. Examples: ...

  5. 【LeetCode】3&period; Longest Substring Without Repeating Characters

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

  6. leetcode题解 3&period; Longest Substring Without Repeating Characters

    题目: Given a string, find the length of the longest substring without repeating characters. Examples: ...

  7. 【LeetCode】3&period; Longest Substring Without Repeating Characters &lpar;2 solutions&rpar;

    Longest Substring Without Repeating Characters Given a string, find the length of the longest substr ...

  8. 《LeetBook》leetcode题解&lpar;3&rpar;&colon;Longest Substring Without Repeating Characters&lbrack;M&rsqb;——哈希判断重复

    我现在在做一个叫<leetbook>的免费开源书项目,力求提供最易懂的中文思路,目前把解题思路都同步更新到gitbook上了,需要的同学可以去看看 书的地址:https://hk029.g ...

  9. LeetCode OJ:Longest Substring Without Repeating Characters(最长无重复字符子串)

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

  10. 【LeetCode】003&period; Longest Substring Without Repeating Characters

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

随机推荐

  1. 设计模式-01-MVC

    概述 Model-View-Controller(MVC),即模型-视图-控制器. MVC将软件系统分成三大部分:Model,View,Controller,三个部分通过某种机制通信 M.V.C的职能 ...

  2. WEB的进击之路-第一章 HTML基本标签(1)

    一.HTML简介 超文本标记语言,标准通用标记语言下的一个应用. "超文本"就是指页面内可以包含图片.链接,甚至音乐.程序等非文字元素. 超文本标记语言的结构包括"头&q ...

  3. Java爬虫--Https绕过证书

    https网站服务器都是有证书的. 是由网站自己的服务器签发的,并不被浏览器或操作系统广泛接受. 在使用CloseableHttpClient时经常遇到证书错误(知乎的网站就是这样) 现在需要SSL绕 ...

  4. form表单样式

    <BODY> <div id="modify-data"> <form class="modify-data-form"> ...

  5. 采用CAS算法 实现高性能的Disruptor 完成多线程下并发、等待、先后等操作

    来源:https://blog.csdn.net/tianyaleixiaowu/article/details/79787377 拓展: https://www.jianshu.com/p/d24b ...

  6. Shooting Contest 射击比赛 &lbrack;POJ1719&rsqb; &lbrack;CEOI1997&rsqb; &lbrack;一题多解&rsqb;

    Description(下有中文题意) Welcome to the Annual Byteland Shooting Contest. Each competitor will shoot to a ...

  7. vue 项目全局修改element-ui的样式

    引入了element-ui,但是和我们自己的样式颜色有很大的不同, 修改例子:在src文件下创建 element-var.scss,代码如下 $--color-primary: yellow;  /* ...

  8. sqoop学习笔记

    #################################################################################################### ...

  9. Quartz&lowbar;TimeJob例子(C&num;)

    执行入口: using System; using System.Collections.Generic; using log4net; using Quartz; using ypt_base.Co ...

  10. oracle&lowbar;set&lowbar;autocommit

    preface 1.centos  operating  system. 2.database is oracle 11g. 3.oracle account  is  scott. step 1.e ...