stringReduction.cpp

/*
http://www.careercup.com/question?id=12718665
String Reduction 
Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? 

Sample Input: 
cab 
bcab 
ccccc

Sample Output: 
2 
1 
5 

Explanation: 
For the first case, you can either get cab -> cc or cab -> bb, resulting in a string of length 2. 
For the second case, one optimal solution is: bcab -> aab -> ac -> b. No more operations can be applied and the resultant string has length 1. 
For the third case, no operations can be performed and so the answer is 5.

Count the number of occurences of each letter in the input string [numA, numB, numC] 
If two of these counts are 0, then return string.length 
Else if (all counts are even) or (all counts are odd), then return 2 
Else, then return 1

Use math induction:
f(n) when n == 3
aaa : 3, f(n) = n
abc => cc : 2 // all odd or all even
abb => cb => a : 1

f(n+1)
case 1: f(n)+1 = n+1
case 2: all odd/all even => f(n), all even/ all odd => 2
case 3: others => f(n), others => 1

*/
#include <vector>
#include <iostream>
#include <string>
using namespace std;
int stringReduction(string &s) {
    int count[3];
    count[0] = 0;
    count[1] = 0;
    count[2] = 0;
    for (int i = 0; i < s.length(); i++) {
        count[s[i] - 'a']++;
    }
    if ((count[0] == 0 && count[1] == 0)
        || (count[0] == 0 && count[2] == 0)
        || (count[1] == 0 && count[2] == 0))
        return s.length();
    if (count[0] % 2 == count[1] % 2 && count[0] % 2 == count[1] % 2)
        return 2;
    else return 1;
}

int main() {
    string s1 = "cab";
    string s2 = "bcab";
    string s3 = "ccccc";
    
    cout << stringReduction(s1) << endl; // 2
    cout << stringReduction(s2) << endl; // 1
    cout << stringReduction(s3) << endl; // 5
    system("pause");
}