T387303 abc

题目描述

一个只包含 $a,b,c$ 的长度为 $n$ 的字符串 $s$。在 $s$ 中尽可能多的找到 $abc$ 子序列，问最多能获得几个 $abc$ 子序列。

$abc$ 子序列即 $(i,j,k)$ 三元组，其中 $1\le i<j<k\le n，s_i=a,s_j=b,s_k=c$。

输入格式

一个只包含a,b,c的字符串s。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

abcabc

输出 #1

2

输入输出样例 #2

输入 #2

aabbcc

输出 #2

2

说明/提示

记字符串长度是 $n$。

• 对于测试点 $1\sim 4$：$1\le n\le 10$
• 对于测试点 $5\sim 8$：$1\le n\le 1000$
• 对于测试点 $9\sim 10$：$1\le n\le 10^5$