专栏首页算法其实很好玩Day11-字符串-无重复字符最长子串

Day11-字符串-无重复字符最长子串

一 唠唠嗑

周末回了趟家,参加高中好哥们的婚礼来着,时间真是快呀

什么,你问我为什么周末没更?

二 来吧

Q:已知一个字符串,求用该字符串的无重复字符的最长子串(有的要求求长度,今天直接求子串)

这时候你脱口而出:这还不简单,把一个字符串的所有可能结果全列出来,然后根据无重复字符这个条件过滤呗

但其实我们说出来的时候,就知道这肯定不是面试官要的答案,毕竟N^2的时间复杂度

那我们怎么优化呢?

是不是不用列出所有的子串?因为一旦出现重复字符,后面的枚举都没有意义了?

我们可以这样处理逻辑:

1.建立字符哈希char_map,来保存字符数量

2.建立一个,当前满足条件的最长子串,即字符串word

3.建立,遍历到当前字符时,最长的子串,即字符串result,最终返回的就是result

4.建立两个指针(i和begin)都指向字符串第一个字符

5.i指针从头向后遍历字符串,用char_map记录字符数量

如果word中,没出现过该字符:

对word尾部添加该字符,并检查result是否需要更新

如果word中,出现了该字符:

将begin指针向后移动,更新char_map中字符数量,直至当前重复的字符数量重新变回1,更新word,将word赋值为begin与i之间的子串

即,我们维护一个滑动窗口,窗口左边界是begin,右边界是i,向后滑动,遍历一遍字符串,即O(N)时间复杂度。

举例:

对于string = “abcbadab”

1. i -> a

begin -> a

word = "a"

2.i -> b

begin ->a

word = "ab"

3.i -> c

begin -> a

word = "abc"

4.i -> b,此时char_map[b] = 2,于是begin向后移动,直到移动到c,此时char_map[b] = 1, 此时word = “cb”,以此类推。

三 完整代码及注释

//
// Created by renyi on 2019/6/17.
//
#include <iostream>
#include <string>
using namespace std;

string longestSubString(string s){
    int begin = 0;//窗口的头指针,即窗口左边界
    string word = "";//记录当前满足条件的最长子串
    string result = "";//记录结果
    int char_map[128] = {0};//记录字符数量的字符哈希

    for (int i = 0; i < s.length(); i++) {
        char_map[s[i]]++;
        if (char_map[s[i]] == 1){//word中没出现过该字符
            word += s[i];//把当前字符添加进word
            if (result.length() < word.length()){
                result = word;//如果word长度超过了当前result长度,则重新赋值result
            }
        } else{//当word中重复出现了该字符
            while (begin < i && char_map[s[i]] > 1){
                char_map[s[begin]]--;//当该字符的字符哈希值,即数量大于1的时候,将begin持续向右移动,知道begin与i维护的滑动窗口中,该字符数量为1
                begin++;
            }
            word = "";
            for (int j = begin; j <= i; j++) {
                word += s[j];//重置word为begin与i维护的滑动窗口之间的字符串,此时word内不包含重复字符,继续向后遍历
            }
        }
    }
    return result;
}

int main(){
    string string1 = "abcdabcabbcdefgaaaaaaa";
    string result = longestSubString(string1);
    cout << result << endl;
    return 0;
}

运行结果

修改字符串为

string string1 = "abcdabcabcdefgaaa";

此时再次运行,结果为

本文分享自微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi),作者:BUPTrenyi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day12-字符串-重复的DNA序列

    Q:将DNA序列看作是只包含【'A', 'C', 'G', 'T'】4个字符的字符串。现有一个这样的字符串,找到所有长度为10且出现次数超过1的子串。

    BUPTrenyi
  • Day7-线性表-堆-寻找中位数

    1.添加元素:void addNum(int num),将num添加进数据结构中

    BUPTrenyi
  • Day22-图算法-图的深搜和宽搜

    从图中某个顶点V出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发,深度优先搜索遍历图,直至图中所有和V有路径相通,且未被访问的顶点,...

    BUPTrenyi
  • Leetcode 211 Add and Search Word - Data structure design

    Design a data structure that supports the following two operations: void addWor...

    triplebee
  • Leetcode 208 Implement Trie (Prefix Tree) 字典树

    Implement a trie with insert, search, and startsWith methods. Note: You may ...

    triplebee
  • Bytes 陷阱, Redis 数据类型的一个小坑

    在Python 3环境下,当我们把一个字符串写进 Redis 再读出来,会发现这个字符串变成了 bytes型的数据:

    青南
  • jQuery框架漏洞全总结及开发建议

    jQuery是一个快速、简洁的JavaScript框架,是一个丰富的JavaScript代码库。jQuery设计的目的是为了写更少的代码,做更多的事情。它封装J...

    Jayway
  • HanLP《自然语言处理入门》笔记--2.词典分词

    笔记转载于GitHub项目:https://github.com/NLP-LOVE/Introduction-NLP

    mantch
  • LeetCode 208. Implement Trie (Prefix Tree)

    ShenduCC
  • 《面向模式的软件体系结构 卷2:用于并发和网络化对象的模式》

    中间件是Web服务、分布式对象、协同应用程序、电子商务系统以及其他重要平台的基础。开发并发与联网中间件和应用程序过程中面临的关键问题有服务访问与配置、时间处理、...

    用户3157710

扫码关注云+社区

领取腾讯云代金券