Last week it was a simple problem that we discussed to tangle our brain.

Reverse only alphabets in a provided string in a most efficient way. (Special characters, numbers, etc should continue to stay at their original place)

First thought …

Okay, so first thought was to make use of an extra space and then we can get our desired result with two traversals of the string. Yeah, but let’s optimize.

Updated thought …

We can make the swaps in place in a single traversal. A good stopping criteria seems to be when index while moving from front crosses the index moving backwards from end.

Let’s write code:

static void Main(string[] args)
{
    Console.WriteLine($"Please enter a string:");

    // Ignore casing
    var inputString = Console.ReadLine().ToLower();
    char[] inputArray = inputString.ToCharArray();
    ReverseAlphabetsOnly(inputArray);        
    Console.WriteLine(
            $"Reversed: {new String(inputArray)}");
}

static void ReverseAlphabetsOnly(char[] inputArray)
{
    int frontIndex = 0;
    int endIndex = inputArray.Length-1;
    char temp;

    while(frontIndex < endIndex)
    {
        if(!IsAlphabet(inputArray[frontIndex]))
            frontIndex++;
        else if(!IsAlphabet(inputArray[endIndex]))
            endIndex--;    
        else
        {
            temp = inputArray[frontIndex];
            inputArray[frontIndex] 
                 = inputArray[endIndex];
            inputArray[endIndex] = temp;

            frontIndex++;
            endIndex--;
        }
    }
}

static bool IsAlphabet(char x) 
{ 
    return ( (x >= 'a' && x <= 'z') 
            || (x >= 'A' && x <= 'Z') ); 
}

// Input:  Le@rn By In$ig#t...
// Output: tg@in Iy Bn$re#L...

Closure …

Approach looks good, as it would be at maximum a single traversal with no extra space used. Thus we are able to solve it with an overall Order of Time complexity O(n) & Space complexity O(1).

Happy solving …

samples GitHub Profile Readme
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight
Matplotlib plot samples
Sandeep Mewara Github Repositories

There are many programming techniques, which when applied appropriately to specific situation, leads to efficient results (either time wise or space wise or both). Dynamic Programming (DP) is one such optimization concept.

Not to be confused with Dynamic programming language or Dynamic type in C#

What is?

Dynamic programming is solving a complicated problem by breaking it down into simpler sub-problems and make use of past solved sub-problems.

Dynamic Programming is mainly an optimization over plain recursion.

Let’s use Fibonacci series as an example to understand this in detail.

Fibonacci Series is a sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

0, 1, 1, 2, 3, 5, 8, 13, 21…

When to?

It is best applied to problems that exhibits Overlapping Subproblems & Optimal Substructure.

Following is how our Fibonacci problem fib(4) breakdown would look like:

We can see that fib(0), fib(1) & fib(2) are occurring multiple times in the graph. These are overlapping subproblems.

Binary search tree would not fall into same category. There would no common subproblem by binary search definition itself.

We can see for optimal solution of fib(4), we would need optimal solution of fib(3) & fib(2) and so on. This tells it has optimal substructure.

Longest path problem does not exhibit as such. Optimal solution for longest distance between A & C might not be optimal for B & C that involves A.

How to?

It’s not an unknown or a new technique. Our brain do it almost all the time. Let’s use Fibonacci series as an example to understand this and then we will apply DP to solve it programmatically.

Logically …

Let’s say, I ask, what is the 4th number in the Fibonacci series? You would work from 0, 1, 1, etc and come to fib(4) = 2. Now, if I ask, what is the 5th number? Would you restart from 0, 1, 1..? Or you would just make use of fib(4) you just solved and get fib(5)?

You see – it’s obvious, you will make use of previous solved result and right away come up with fib(5) instead of starting from 0. In programming language, this is tabulation using calculated fib(4) & fib(3).

Tabulation is a technique of starting from smallest sub-problem and storing the results of entries until target value is reached.

Let’s say, now I ask to calculate fib(8). Our natural way of working on it would be to first find fib(7) & fib(6). In order to know fib(7), we will figure out fib(6) & fib(5) and hence forth. With fib(7), we already traversed through fib(6). This is another approach where we calculated the next subproblem and keep on storing them in case of need later. In programming language, this is memoization.

Memoization is a technique of storing the results of expensive function calls and returning the cached result when the same inputs occur again.

DP breaks the problem into sub-problems and uses memoization or tabulation to optimize. We will understand about them with examples below.

Programmatically in action …

In order to compare the optimization cost, we will use recursion as another way to solve the problem.

static void Main(string[] args)
{
    Stopwatch stopwatch = new Stopwatch();

    Console.WriteLine($"Fibonacci Recursive:");
    for (int i = 30; i <= 50; i+=5)
    { 
        stopwatch.Reset();
        stopwatch.Start();
        var _ = FibonacciRecursive(i);
        stopwatch.Stop();
        Console.WriteLine($"{i}th took time: ({stopwatch.Elapsed})");
    }

    Console.WriteLine($"Dynamic Programming:");
    for (int i = 30; i <= 50; i+=5)
    { 
        stopwatch.Reset();
        stopwatch.Start();
        var _ = FibonacciDPTabulation(i);
        stopwatch.Stop();
        Console.WriteLine($"{i}th took time: ({stopwatch.Elapsed})");
    }
}

static long FibonacciRecursive(int number)
{
    if (number <= 1)
        return number;
    return FibonacciRecursive(number-2) + FibonacciRecursive(number - 1);
}

static long FibonacciDPTabulation(int number)
{
    long[] arr = new long[100];
    arr[0] = 1; arr[1] = 1; 
    for( int x=2; x <= number; x++)
    {
        arr[x] = arr[x-1] + arr[x-2];
    }
    return arr[number];
}

With above code, we got the following output:

Difference is astonishing! DP is too fast in comparison. Just look at the 50th time difference.

With simple iterative approach, Fibonacci Series can be calculated in the same ballpark time as of DP. Current example is just to keep things simple and to understand the DP concept. Please look at the end of post for common examples that would clarify where DP would be of real help over recursion. (& iterative approach would be difficult to code)

Above approach of DP is considered Bottom-Up approach as we started with bottom (lowest term) and then moved to the highest one. This is tabulation. We keep on filling on the cache here till we reach the target.

Alternatively, there is a Top-down approach. We start solving from highest term and store solutions of sub problems along the way. This is memoization. A code for this approach would look like:

private static Dictionary<int, long> memo 
                    = new Dictionary<int, long>();

static long FibonacciDPMemoization(int number)
{
    if (number == 0 || number == 1) {
        return number;
    }
    
    // see if we've already calculated this
    if (memo.ContainsKey(number)) {                
        return memo.GetValueOrDefault(number);
    }

    long result = FibonacciDPMemoization(number - 1) 
                + FibonacciDPMemoization(number - 2);
    memo.Add(number, result);

    return result;
}

memoization is sometimes simpler to understand and write code because of it’s natural way of solving.

Generally, tabulation outperformes memoization by a constant factor. This is because of no overhead for recursion and can be stored as a pre-allocated array. We first calculate and store the value of a sub problem repeated most number of times here.

Few Common Examples?

• Tower of Hanoi
• Checkerboard
• Egg dropping puzzle
• Matrix chain multiplication

Details of these above problem can be read here.

Beware?

Apart from avoiding problems that do not have Overlapping Subproblems & Optimal Substructure, one need to understand we are doing a trade here – space for time!

We can always discuss that though DP is using extra space to store the sub-problems data, but in turn helps save in memory calculation which could be expensive. Thus, in case of constrained space, we need to evaluate usage of DP.

Keep learning!

samples GitHub Profile Readme
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight
Matplotlib plot samples

Often in our group we discuss about puzzles or problems related to data structure and algorithms. One such day, we discussed about:

how will we find if any anagram of a string is palindrome or not?

Our first thought went in the direction to start from first character and then traverse till end to see if there could be matching pair. Keep track of it, move to next character till middle and then stitch all to figure if so. It solves, but the query was – could it be solved better though?

Of course! With putting some stress on the brain, it turned out that in a single read, we will have info enough, to tell, if any anagram formed from the input string can be a palindrome or not.

Thought converted to Code

static void CheckIfStringAnagramHasPalindrome()
{
    Console.WriteLine($"Please enter a string:");

    // Ignore casing
    var inputString = Console.ReadLine().ToLower();

    // Just need to keep track of unique characters
    var characterSet = new HashSet<char>();

    // Single traversal of input string 
    for(int i=0; i<inputString.Length; i++)
    {
        char currentCharacter = inputString[i];
        if(characterSet.Contains(currentCharacter))
            characterSet.Remove(currentCharacter);
        else
            characterSet.Add(currentCharacter);
    }

    // Character counts in set will help 
    // identify if palindrome possible 
    var leftChars = characterSet.Count;
    if(leftChars == 0 || leftChars == 1)
        Console.WriteLine($"YES - possible.");
    else
        Console.WriteLine($"NO - Not possible.");
}

Approach looked good, as with a single traversal and usage of HashSet, i.e. with overall Order of Time complexity O(n) & Space complexity O(1), we were able to solve it.

It was fun solving!

GitHub Profile Readme Samples
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight