Logic in Min String and 1count

#1

how to solve this problem
ques link https://hack.codingblocks.com/contests/c/526/1027

and how to solve this
https://hack.codingblocks.com/contests/c/526/916

#2

For MinString,
It can be observed that the length of minimum string is either <= 2 or equal to the length of original string and there can be no case such that 2 < minimum string length < original string length. If the string cannot be reduced further, then all letters in the string are the same and stringLength is the final answer.
If each letter of the string is present an odd amount of times, after one reduction step, they shall all be present an even amount of times. The converse is also true, that is, if each letter of the string is present an even amount of times, they shall be present an odd amount of times after one reduction step.
Now if all characters are present an even number of times, or an odd number of times, the only answer that is possible is 2, because (0, 2, 0) is (even, even, even) while (0, 1, 0) is (even, odd, even) so only 2 preserves this evenness.
In any other condition, the answer becomes 1.

1 Like
#3

Thanks for a nice explanation.Can u also tell why in all the cases other than (all odds) / (all evens) / (all same characters)
the answer would be 1 ???

#4

As told earlier, the length of minimum string is either <= 2 or equal to the length of original string, or 2 < minimum string length < original string length is never true. So, for the cases other than (all odds) / (all evens) / (all same characters), the answer would be 1.