Crisp String
Contest: Educational Codeforces Round 60 (Rated for Div. 2)
Difficulty rating: 2500
Tags: bitmasks, dp

You are given a string of length $$$n$$$. Each character is one of the first $$$p$$$ lowercase Latin letters.

You are also given a matrix $$$A$$$ with binary values of size $$$p \times p$$$. This matrix is symmetric ($$$A_{ij} = A_{ji}$$$). $$$A_{ij} = 1$$$ means that the string can have the $$$i$$$-th and $$$j$$$-th letters of Latin alphabet adjacent.

Let's call the string crisp if all of the adjacent characters in it can be adjacent (have 1 in the corresponding cell of matrix $$$A$$$).

You are allowed to do the following move. Choose any letter, remove all its occurrences and join the remaining parts of the string without changing their order. For example, removing letter 'a' from "abacaba" will yield "bcb".

The string you are given is crisp. The string should remain crisp after every move you make.

You are allowed to do arbitrary number of moves (possible zero). What is the shortest resulting string you can obtain?

Input format:
The first line contains two integers $$$n$$$ and $$$p$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le p \le 17$$$) — the length of the initial string and the length of the allowed prefix of Latin alphabet.

The second line contains the initial string. It is guaranteed that it contains only first $$$p$$$ lowercase Latin letters and that is it crisp. Some of these $$$p$$$ first Latin letters might not be present in the string.

Each of the next $$$p$$$ lines contains $$$p$$$ integer numbers — the matrix $$$A$$$ ($$$0 \le A_{ij} \le 1$$$, $$$A_{ij} = A_{ji}$$$). $$$A_{ij} = 1$$$ means that the string can have the $$$i$$$-th and $$$j$$$-th letters of Latin alphabet adjacent.

Output format:
Print a single integer — the length of the shortest string after you make arbitrary number of moves (possible zero).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example no letter can be removed from the initial string.

In the second example you can remove letters in order: 'b', 'c', 'a'. The strings on the intermediate steps will be: "abacaba" $$$\rightarrow$$$ "aacaa" $$$\rightarrow$$$ "aaaa" $$$\rightarrow$$$ "".

In the third example you can remove letter 'b' and that's it.

In the fourth example you can remove letters in order 'c', 'b', but not in the order 'b', 'c' because two letters 'c' can't be adjacent.

Example input:
7 3
abacaba
0 1 1
1 0 0
1 0 0

Example output:
7

Example input:
7 3
abacaba
1 1 1
1 0 0
1 0 0

Example output:
0

Editorial:
Each state of the string can be denoted as the set of characters we deleted from it, and each such set can be represented as a $$$p$$$-bit binary mask, where $$$i$$$-th bit is equal to $$$0$$$ if $$$i$$$-th character of the alphabet is already deleted, and $$$1$$$ otherwise.
Let's call a mask bad if the string formed by this mask is not crisp. Let's also say that a pair of characters $$$a, b$$$ forbids mask $$$m$$$ if $$$a, b$$$ is a pair of characters that should not be adjacent, but they are adjacent in the string formed by mask $$$m$$$.
If we somehow find all bad masks, then the solution would be writing simple bitmask dp to find the best mask that is not bad and reachable from the initial mask (the one having all bits set to $$$1$$$). So let's focus on finding all bad masks. Obviously, if some pair of characters forbids a mask, then it's bad, and vice versa.
Let's pick some pair of characters $$$a, b$$$ and find all masks forbidden by it (we will do the same for every pair of characters that cannot be adjacent). Let's check every occurence of $$$a$$$ in the initial string. For each occurence, we will find the closest occurence of $$$b$$$ to the right of it. If there's no any, or if there's another $$$a$$$ between them, let's ignore the occurence of $$$a$$$ we have chosen and move to the next one. Otherwise, let's find all characters that occur at least once between the fixed occurences of $$$a$$$ and $$$b$$$. If all those characters are deleted, then these occurences of $$$a$$$ and $$$b$$$ will be adjacent — so pair $$$a, b$$$ forbids any mask that has bits representing $$$a$$$ and $$$b$$$ set to $$$1$$$, bits representing every character occuring in between to $$$0$$$, and all other bits to any values. Let's mark all these masks as forbidden as follows: we will write a recursive function $$$mark(m, a, b)$$$ that marks mask $$$m$$$ and every its submask that has bits $$$a$$$ and $$$b$$$ set to $$$1$$$ as forbidden. This function should check if $$$m$$$ is not forbidden; if not, then mark it as forbidden, iterate on the bit $$$i$$$ we may remove from $$$m$$$, and call $$$mark(m \oplus 2^i, a, b)$$$ recursively (but only if $$$i$$$ is set to $$$1$$$ in mask $$$m$$$, and if $$$i \ne a$$$ and $$$i \ne b$$$). If we implement it in such a way, then for each pair $$$a, b$$$, it will take $$$O(n + p 2^p)$$$ operations to mark all masks forbidden by this pair of characters, so overall complexity will be $$$O(np^2 + p^3 2^p)$$$ or $$$O(np + p^3 2^p)$$$, depending on your implementation.