‹ 上一题 下一题 ›

g5-08284. 最长不重复片段 未做

1000 ms 256 MB 测试点 10 通过率 100% GESP-55级·STLunordered_map

题目描述

一个小写字母串 。找出最长连续片段(子串),要求片段内没有重复字符,输出它的长度。

滑窗做法:左端 left、右端 i 都只前进。右端每纳入一个字符 c,若 c 上次出现的位置落在窗口内,左端就得跳到「上次出现位置的下一位」;但 left 只能前进不能后退——所以要和当前 left 取较大者。用 unordered_map<char,int> 记每个字符上次出现的位置。

输入格式

一行一个字符串 (,只含小写字母)。

输出格式

一行一个整数:最长无重复片段的长度。

样例

输入:

abba

输出:

2

最长的不重复片段是 ab 或 ba,长度 2;再长的片段都会撞上重复字符。

数据范围

,只含小写字母。提示:拿 abba 走一遍—— 遇到第二个 b,left 跳到 2; 遇到第二个 a,它上次出现在 0(已在窗外),left 不能退回 1,取较大者后仍是 2。

输入
输出

            
答案