Day4 Prb I

#include <bits/stdc++.h>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

typedef long long int ll;

const ll mod = 1e9+7;

#define pi atan(1)*4
#define sc scanf
#define pf printf
#define fin for(ll i=0; i<n; i++)
#define fiz for(ll i=n-1; i>=0; i--)
#define fjm for(ll j=0; j<m; j++)
#define fr(i,a,n) for(ll i=a; i<n; i++)
#define pb push_back
#define pb2(x,y) push_back(make_pair(x,y))
#define INF 1e18
#define nl '\n'
#define sz(a) a.size()
#define readfirst() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define make(a,n) memset(a, n, sizeof(a))
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define fixpre(x) fixed << setprecision(x)

void OJ() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r", stdin);
    freopen("output.txt","w", stdout);
    #endif
}

ll gcd(ll p, ll q) {
    return q==0?p:gcd(q,p%q);
}

bool isPowerOfTwo(ll n) {
   if(n==0) return false;
   return (ceil(log2(n)) == floor(log2(n)));
}

ll power(ll a, ll n) {
    if(n==1) return a%mod;
    ll x=power(a,n/2);
    if(n%2==0) return (x*x)%mod;
    else return (x*x)%mod*a%mod;
}

ll digitSum(ll n) {
    ll s=0;
    while(n>0) {
        s+=n%10;
        n/=10;
    }
    return s;
}

ll fact(ll n){
    return tgamma(n + 1);
}

bool isPrime(ll n) {
    if (n <= 1) return false;
    for (ll i=2; i*i<=n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    auto st = clock();
    readfirst();
    OJ();

    ll testcase=1, count=1;
    // cin >> testcase;
    // cin.ignore();
    while(testcase--) {
        // cout << "Case " << count++ << ": ";
        string s, ss="";
        cin >> s;
        ss+=s[0];
        ll ans=1, n=sz(s);
        map<char,vector<ll>> m;
        map<char,ll> mm;
        mm[s[0]]++;
        m[s[0]].pb(0);
        ll in;
        // cout << ss << nl;
        for(ll i=1; i<n; i+=in) {
            ll last;
            if(s==ss) break;
            map<char,ll> mmm;
            mmm=mm;
            for(ll j=i; j<n; j++) {
                if(j==i) {
                    if(!sz(m[s[j]])) {
                        ss+=s[j];
                        // cout << "Chk1 " << count++ << " : " << ss << nl;
                        m[s[j]].pb(sz(ss)-1);
                        mm[s[j]]++;
                        mmm[s[j]]--;
                        ans++;
                        in=1;
                        break;
                    }
                    else{
                        last=m[s[j]].front();
                        mmm[s[j]]--;
                    }
                    if(j==n-1) {
                        string tt=s.substr(i,j-i+1);
                        for(auto k:tt) {
                            ss+=k;
                            m[k].pb(sz(ss)-1);
                            mm[k]++;
                            mmm[k]--;
                        }
                        // cout << "Chk2 " << count++ << " : " << ss << nl;
                        ans++;
                    }
                }
                else {
                    ll r=-1;
                    for(auto k:m[s[j]]) {
                        if(k>r) r=k;
                    }
                    if(!sz(m[s[j]]) || r<last) {
                        string tt=s.substr(i,j-i);
                        for(auto k:tt) {
                            ss+=k;
                            m[k].pb(sz(ss)-1);
                            mm[k]++;
                            mmm[k]--;
                        }
                        // cout << "Chk3 " << count++ << " : " << ss << nl;
                        ans++;
                        in=j-i;
                        break;
                    }
                    else {
                        if(j==n-1 && mmm[s[j]]) {
                            string tt=s.substr(i,j-i+1);
                            for(auto k:tt) {
                                ss+=k;
                                m[k].pb(sz(ss)-1);
                                mm[k]++;
                                mmm[k]--;
                            }
                            // cout << "Chk4 " << count++ << " : " << ss << nl;
                            ans++;
                            break;
                        }
                        ll temp=last;
                        for(auto k:m[s[j]]) {
                            if(k>last) {
                                last=k;
                                break;
                            }
                        }
                        if(last==temp) {
                            string tt=s.substr(i,j-i);
                            for(auto k:tt) {
                                ss+=k;
                                m[k].pb(sz(ss)-1);
                                mm[k]++;
                                mmm[k]--;
                            }
                            // cout << "Chk5 " << count++ << " : " << ss << nl;
                            ans++;
                            in=j-i;
                            break;
                        }
                    }
                }
            }
        }
        // cout << ss << nl;
        // set<char> sss;
        // for(auto i:ss) {
        //     sss.insert(i);
        // }
        cout << ans << nl;
        // for(auto i:sss) {
        //     cout << i << " : ";
        //     for(auto j:m[i]) cout << j << " ";
        //     cout << nl;
        // }
    }


    // while(cin >> n) {
    //     if(n==0) break;

    // }
    cerr << 1.0 * (clock()-st) / CLOCKS_PER_SEC << " Seconds" << nl;
    return 0;
}