gistfile1.cpp

class LittleElephantAndBallsAgain {
public:
  int getNumber(string);
};
 
set<string> memo;
map<string, int> dp;
 
int func(string s) {
  if (memo.count(s)) {
    return dp[s];
  } else {
    int i;
    
    set<char> st;
    
    memo.insert(s);
    
    for (i = 0; i < (int) s.size(); i++) {
      st.insert(s[i]);
    }
    
    if (st.size() == 1) return 0;
    
    dp[s] = func(s.substr(1, s.size() - 1)) + 1;
    dp[s] = min(dp[s], func(s.substr(0, s.size() - 1)) + 1);
    
    return dp[s];
  }
}
 
int LittleElephantAndBallsAgain::getNumber(string S) {
  return func(S);
}