# Explanation in simple english and solution in C#

• 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];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.