Substitution cipher algorithm performance boost
You should use memoization on findNextPossible(), otherwise your algorithm has exponential complexity.

Also: the optimization obtained by looking for '0's will be no more useful once you use memoization... so the resulting code should become much, much smaller.

This is a possible implementation:

#include &lt;string&gt;
#include &lt;map&gt;
#include &lt;iostream&gt;
#include &lt;cassert&gt;

using namespace std;

int ways(std::string s) {
  static map&lt;string,int&gt; cache;
  map&lt;string,int&gt;::const_iterator f = cache.find(s);
  if (f!=cache.end()) return f-&gt;second;
  //  cout&lt;&lt;"ways("&lt;&lt;s&lt;&lt;")"&lt;&lt;endl;                                                                                                            
  if (s.size()==0) return 1;
  if (s[0]=='0') return 0; // no way the first digit is 0                                                                                     
  if (!isdigit(s[0])) return 0;
  if (s.size()==1) return 1; // only one possibility for a single digit                                                                       
  // here we have at least 2 digits                                                                                                           
  if (!isdigit(s[1])) return 0;
  int n = 10*(s[0]-'0')+(s[1]-'0');
  if (n&gt;26) return cache[s] = ways(s.substr(1)); // cannot merge first two digits.                                                                       
  return cache[s] = ways(s.substr(1)) + ways(s.substr(2)); // two possible interpretations                                                               
}

const char *tests[]={"1213","12","214","205",0};

int main() {
  for (int i = 0; tests[i]; ++i) {
    cout&lt;&lt;tests[i]&lt;&lt;": "&lt;&lt;ways(tests[i])&lt;&lt;endl;
  }
}