First think of a worst case input:

abcdefgh

In this case, there's no scope of optimization as all characters are different. Hence printer would print character by character.

Now consider a slightly better case:

abcdafgh

In above input, notice that character 'a' is repeated. So, you could visualize that printer should first type 'a' till position 4 (0 index based) to print in minimal turns.

Try to generalize above solution for range p to r substring. It should me

- minimum of P[p+1, r] + 1 (case where we assume that first character should not be optimized at all).
- minimum of (P[p, q-1], P[q+1, r]) where q ranges from p+1 to r and s[p] equals s[q]. In this case, we are trying all combinations by optimizing for position p.
- Finally P[p,r] is minimum of above two calculations.

```
public int StrangePrinter(string s) {
if (string.IsNullOrEmpty(s))
{
return 0;
}
int[,] P = new int[s.Length, s.Length];
for (int i=0; i < s.Length; i++)
{
P[i,i] = 1;
}
for (int l=2; l <= s.Length; l++)
{
for (int p = 0; p < s.Length - l + 1; p++)
{
int r = p + l - 1;
int min = P[p + 1, r] + 1;
for (int q = p + 1; q <= r; q++)
{
if (s[p] == s[q])
{
int sum = P[p, q-1];
if (q != r)
{
sum += P[q+1, r];
}
if (sum < min)
{
min = sum;
}
}
}
P[p,r] = min;
}
}
return P[0, s.Length-1];
}
```