EDIT - Edit Distance Again

As any experienced programmer must know the famous problem of "Edit Distance", however this problem is considered an “alternating chain” if you have alternately made case sensitive.

Example: "AaAaAbB" "B" "a" "aBaCdEf"

Alternating chains are considered in our problem.

We only have one operation that is permitted in exchange for a lower or upper case Latin letter.

Given a string giving the minimum number of changes to be considered an alternating chain.

Input

A string with no spaces line containing only uppercase and lowercase letters, one for each line of maximum length 10^3 until end of file

Output

For each line print the minimum number of changes to the chain is a "chain alternately"

Example

Input:
AaAaB
ABaa
a

Output:
0
2
0

Added by:Paulo Costa
Date:2012-02-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:PUCP

hide comments
2021-04-18 13:38:09
ez pz AC in one go
2020-06-20 12:48:40
I saw the same problem in hackerrank's "Problem Solving - Intermidate" certification test.
2020-03-30 02:50:38
pure Ad-hoc
AC in one go

Last edit: 2020-03-30 02:51:27
2018-07-01 03:09:23
Can anyone explain why the result for test case "ABaa" is 2?
I think it is 1, one move ABaa->AaBa or ABaa->aBaA.
2018-05-25 07:36:34
Solved it! But the leaderboard is filled with 0.00s time while I got 0.01s even though my solution is O(n).
Here's my code <snip>

Last edit: 2022-08-10 17:01:49
2017-05-30 17:10:25
@daman007
do something like this
/*****************/
main()
{string s;
while(cin>>s)
{//your code here
}
}
/*******************/
2017-05-12 21:53:43
Number of testcases is not given here, So can anyone tell me how can I stop taking input
2017-03-03 20:27:55
The statement is of very poor quality, but got AC first try so it's not bugged.
2017-02-22 15:52:02
Again and again it is showing WA ??
same type of problem I solved on codechef was accepted in one Go :/

Last edit: 2017-02-22 15:52:15
2016-06-27 00:10:35
This is not even remotely a DP problem. Pure Ad-hoc.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.