알파벳 문자열

s에 소문자를 최소한으로 삽입해서, 일부 글자를 지우면 a부터 z까지 순서대로 남도록 만든다.

보통5동적 계획법문자열그리디이분 탐색면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

소문자로만 이루어진 문자열에서 문자 몇 개를 지워 a부터 z까지가 순서대로 남게 만들 수 있으면, 그 문자열을 알파벳 문자열이라고 한다.

문자열 ss가 주어진다. ss의 아무 위치에나 소문자를 끼워 넣어 알파벳 문자열로 만들려고 한다. 넣어야 하는 문자의 최소 개수를 구하라.

입력

입력은 테스트 케이스 하나로 이루어진다. 같은 프로그램이 서로 다른 입력으로 여러 번 실행될 수 있다.

첫째 줄에 소문자로만 이루어진 문자열 ss가 주어진다. (1s501 \le |s| \le 50)

출력

ss를 알파벳 문자열로 만들기 위해 넣어야 하는 문자의 최소 개수를 한 줄에 출력한다.