g6-07901. 划分字符串·优化 未做

给定一个只含小写字母的字符串 $s$。把它分成若干连续段，要求每一段内没有重复字母。求最少分成几段。

本题的 $|s|$ 较大，需要 $O(n)$ 或 $O(n\log n)$ 的做法。

一行一个字符串 $s$。

一行一个整数，表示最少段数。

输入 1

abac

输出 1

2

对于所有数据，$1\le |s|\le 100000$。