AlgoMooc
← 返回题库

K0063. 无重复字符连续子串

中等通过率 35% · 提交 105 · 通过 37
滑动窗口双指针哈希表字符串

小慕正在开发一个魔法符号分析系统,系统需要处理由字母组成的符号序列。在项目中,小慕遇到了一个关键问题:给定一个符号序列,他需要统计其中所有不含重复字符的连续的数量。子串越长,蕴含的魔法能量越强。小慕必须根据符号的结构和规则,计算出所有的个数。

提示:带虚线的词点一下有通俗解释。

输入描述

输入一个由小写字母组成的字符串`str`,表示魔法符号。字符串的长度不超过20000。

输出描述

输出一个整数,表示无重复字符的连续子串的个数。

示例

示例 1

输入

abac

输出

8

说明:所有子串是 `a`, `ab`, `aba`, `abac`, `b`, `ba`, `bac`, `a`, `ac`, `c`。其中无重复字符的子串为:`a`, `ab`, `b`, `ba`, `bac`, `a`, `ac`, `c`,总个数为8。

示例 2

输入

xbmxbnh

输出

21

说明:所有子串是 `x`, `xb`, `xbm`, `b`, `bm`, `bmx`, `m`, `mx`, `mxb`, `mxbn`, `mxbnh`, `x`, `xb`, `xbn`, `xbnh`, `b`, `bn`, `bnh`, `n`, `nh`, `h`。其中无重复字符的子串为:`x`, `xb`, `xbm`, `b`, `bm`, `bmx`, `m`, `mx`, `mxb`, `mxbn`, `mxbnh`, `x`, `xb`, `xbn`, `xbnh`, `b`, `bn`, `bnh`, `n`, `nh`, `h`,总个数为21。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。