using System;

​

public class Program

{

    public static void Main(string[] args)

    {

        Console.WriteLine("banana " + Solution("banana"));

        Console.WriteLine("axbdce " + Solution("axbdce"));

        Console.WriteLine("abcdaaaaaaaaaaaaaa " + Solution("abcdaaaaaaaaaaaaaa"));

        Console.WriteLine("bbbbaa " + Solution("bbbbaa"));

    }

​

    public static int longestSubsequenceWithActualSolution(string arr)

    {

        int[] T = new int[arr.Length];

        int[] actualSolution = new int[arr.Length];

        for (int i = 0; i < arr.Length; i++)

        {

            T[i] = 1;

            actualSolution[i] = i;

        }

​

        for (int i = 1; i < arr.Length; i++)

        {

            for (int j = 0; j < i; j++)

            {

                if (arr[i] >= arr[j])

                {

                    if (T[j] + 1 > T[i])

                    {

                        T[i] = T[j] + 1;

                        //set the actualSolution to point to guy before me

                        actualSolution[i] = j;

                    }

                }

            }

        }

​

        //find the index of max number in T 

        int maxIndex = 0;

        for (int i = 0; i < T.Length; i++)

        {

            if (T[i] > T[maxIndex])

            {

                maxIndex = i;

            }

        }

        return T[maxIndex];

    }

​

    public static int Solution(string input)

    {

        int longestIncrLength = longestSubsequenceWithActualSolution(input);

        return input.Length - longestIncrLength;

    }

}