# Find number of combinations of strings

This was an interview question I was asked. My answer is below, but I wonder if there is a more efficient way. Possible a combinatorics type function, or is an exhaustive generation + count the only way?

Rules: Given a character, the next character can be any one of How many N character combinations can you make? For example

• a -> i,e

• e -> i,o

• i -> a,e,o

• u -> a,e,i,o

• o -> i,u,o

For N = 1 possible string combinations are a , e, i ,o ,u for N = 2 possible string combinations are [ai, ae], [ei ,eo] ,[ia , ie , io],[ua,ue,ui,uo],[oi,ou,oo] and so on. I solved it by constructing a tree and then counting the leaves

struct Node {
Node(char v) : v_(v) {}
void                     add_child(shared_ptr<Node> n) { children.emplace_back(n); }
char                     v_ = 0;
vector<shared_ptr<Node>> children;
};

void add_child(shared_ptr<Node> root, int n, int depth, const map<char, vector<char>> &combo) {
if (depth == n) return;
auto ch = root->v_;
auto it = combo.find(ch);
for (auto ch : it->second) {
//printf("Adding to %c to %c\n", ch, root->v_);
}
++depth;
for (auto &child : root->children) { add_child(child, n, depth, combo); }
}

int count_leaf(shared_ptr<Node> root) {
if (root->children.size() == 0) return 0;
int sum = 0;
for (auto &child : root->children) sum += count_leaf(child);
return sum > 0 ? sum : root->children.size();
}
// Find combos until this depth
int n = 3;

map<char, vector<char>> combo;
combo.insert(make_pair('a', vector<char>{'i', 'e'}));
combo.insert(make_pair('e', vector<char>{'i', 'o'}));
combo.insert(make_pair('i', vector<char>{'a', 'e', 'o'}));
combo.insert(make_pair('u', vector<char>{'a', 'e', 'i', 'o'}));
combo.insert(make_pair('o', vector<char>{'i', 'u', 'o'}));

// Create a N depth tree and count leaves
// Count all children until n = 3;
auto root  = make_shared<Node>(0);
int  depth = 0;
for (auto &c : combo) { root->add_child(make_shared<Node>(c.first)); }
for (auto child : root->children) { add_child(child, n, depth, combo); }
printf("%d\n", count_leaf(root));
}


Is there a better way. Critique on the code/bugs, and if there's a c++14 idiomatic way of doing it, even better.

• Do you know yet if your solution passed? – yuri Jul 11 '17 at 14:19
• @yuri Not yet, but so far, not found any obvious bugs – Delta_Fore Jul 11 '17 at 14:21

TL;DR: dynamic programming.

If the alphabet has $k$ symbols (5 in the example), in the worst case there are $k^N$ possible strings and generating them is $\Omega(k^N)$. But it's possible to count them in $O(k^2 N)$ time and $O(k^2 + N)$ space using a simple dynamic programming approach.

The input gives the successor function: $a$ must be followed by one of $\{i,e\}$. The first step is to reverse that to get the predecessor function: $a$ must be preceded by one of $\{i,u\}$.

Then the number of strings of length $l$ which end in $a$ is $1$ if $l=1$, or the sum of the number of strings of length $l-1$ which end in $i$ or $u$ otherwise.

Actually, if $N$ is large enough relative to $k$ you can do even better with a more complicated approach. Treat it as a Markov chain and find a matrix power of the $0-1$ matrix which indicates the successor function. That takes $O(\lg N)$ matrix multiplications of a $k\times k$ matrix.

• We can actually use the successor-function directly. – Deduplicator Jul 11 '17 at 17:42