专栏首页菩提树下的杨过算法练习(3)-寻找最大的不重复子串

算法练习(3)-寻找最大的不重复子串

要求:给定1个字符串,比如ababc,要求找出“第1个最长的不重复子串”,即:"abc"

思路:遍历每个字符,寻找以它开头的不重复子串,遍历过程中,可以用一个Set作为缓冲区,存放曾经处理过的起始字符串。

过程:

(a)babc -> 子串为a

(ab)abc -> 子串为ab

(ab)abc -> 发现重复字符a,准备从第2个字符开始新一轮查找

a(b)abc -> 子串为b

a(ba)bc -> 子串为ba

a(ba)bc -> 发现重复字符b,准备第第3个字符开始新一轮查找

ab(a)bc -> 子串为a

ab(ab)c -> 子串为ab

ab(abc) -> 查找结束

代码:

    /**
     * 查找最长不重复子串
     *
     * @param s
     * @return
     */

    public String getFirstLongestSubstring(String s) {
        System.out.println(s);
        char[] arr = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int right = -1, maxLen = -1;
        String subStr = "";
        for (int i = 0; i < arr.length; i++) {
            if (i > 0) {
                //缩小左边界
                set.remove(arr[i - 1]);
            }
            while (right + 1 < arr.length && !set.contains(arr[right + 1])) {
                set.add(arr[right + 1]);
                //扩大右边界
                right++;
            }
            int len = right - i + 1;
            if (len > maxLen) {
                maxLen = len;
                char[] temp = new char[maxLen];
                s.getChars(i, right + 1, temp, 0);
                subStr = new String(temp);
            }
            if (maxLen >= arr.length - i) {
                break;
            }
        }
        return subStr;
    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ruby学习笔记(6)-Array的使用

    ruby的数组基本使用,跟c#中的数组比起来,最不习惯的区别在于允许负索引(跟javascript到有几分相似) arr=[3,4,5,6,7,8,9] pu...

    菩提树下的杨过
  • ZooKeeper 笔记(1) 安装部署及hello world

    先给一堆学习文档,方便以后查看 官网文档地址大全: OverView(概述) http://zookeeper.apache.org/doc/r3.4.6/zo...

    菩提树下的杨过
  • 如何让java中的注释代码执行?

    原因:java编译器会处理unicode字符,\u000d以及\u000a 正好对应“\r”回车、“\n”换行,经过编译器处理后,等效于下面的代码:

    菩提树下的杨过
  • [Go] Golang练习项目-GO语言实现快速排序-第一个数作为基准更容易理解

    1. 第一个数作为基准数,找到所有比基准数小的放在左边 ,找所有比基准数大的放右边

    陶士涵
  • visualStudio 无法登陆

    如果有人用 VS 登 AzureCN 的账户导致 VS 无法登陆MS账户,可以删除C:\Users\【username】\AppData\Local\.Iden...

    林德熙
  • TF 2.1.0-rc2 发布,2020 年停止支持 Python 2

    内容一览:2020 年 1 月 1 日,Python 2 即将停止维护,正式退休。Python 3 全面登场的时刻,TensorFlow 也在悄悄改变。

    HyperAI超神经
  • JVM故障分析及性能优化实战(III)——jstat命令的使用及VM Thread分析

    前面提到了一个使用jstack的shell脚本,通过命令可以很快地定位到指定线程对应的堆栈信息。

    IT技术小咖
  • 这项决定你晋升速度的技能,80%的人都忽略了

    现在的职场竞争越来越激烈,不学上一两门新技能,保持自己知识更新,很容易被年轻后辈超越。有些人选择学一门外语,有些人选择学习职场上为人处事的能力。

    叫我龙总
  • 提升 Python 性能 - Numba 与 Cython

    花下猫语:最近,读者微信群里又频繁聊到了 Python 的性能问题,这真是老生常谈了。我想起自己曾收藏过几篇关于如何提升性能的文章,似乎挺有帮助的,便去联系了下...

    Python猫
  • WSL运行Chrome Headless模式

    Google Chrome早就支持了headless模式,但一般都是在Linux上运行,而我则习惯于在WSL上开发,折腾了好久终于找到了可以在WSL上跑head...

    drunkdream

扫码关注云+社区

领取腾讯云代金券