**Introduction**

There are several problems that cannot be solved using regular algorithms like greedy or divide and conquer, or the solutions they provide are not optimal.

So, we use * Dynamic Programming*, which is an optimisation of simple recursion to solve such problems. The basic idea is to store the results of sub-problems to avoid recalculation and reduce the time complexity of the problems.

This blog will discuss one such problem, Scramble String, which can easily be solved using recursion. This is not the optimised approach as it might give the error of time limit exceeding in case of more significant constraints because of which this method is not suitable. It consumes ample time and space as it makes repetitive calls and uses a stack in the memory. So, we optimise the time and space complexity, and to check whether the string is a scrambled string or not, we will use dynamic programming.

**What is a scrambled string?**

A **Scrambled string** is a string which is obtained after swapping the sibling nodes in the binary representation of a string. We can represent a string * S *in the form of a binary tree by recursively dividing it into two non-empty substrings. To scramble the string, we just have to swap the 2 children of a non-leaf node.

For e.g. We can convert node “ni” and swap its two children. It produces a scrambled string “innja”.

We basically split the string into * 2 *non-empty substrings by choosing a random index of a string

*and dividing it into*

**S***halves, say*

**2***and*

**A***.*

**B**So if we use * A* and

*to reconstruct our original string*

**B***, there are*

**S***possibilities:*

**2**(Order remains same.)**S = A + B**(Order has been reversed.)**S = B + A**

Also Read About, __Byte Array to String__

**Problem Statement**

You are given * 2 *strings

*and*

**S1***and the task is to determine whether*

**S2,***is a scrambled form of string*

**S2***or not.*

**S1**### Example

**S1 = “ACTIVE“**

**S2 = “EVITAC”**

In this case, string **S2 **is the scrambled form of string** S1.**

In this example, we see that we can divide the word “**ACTIVE**” into * 2* halves of length

*and*

**2***and these*

**3***halves can also be divided into*

**2***halves and so on and it forms a recursive tree and in the end, we are left with leaf nodes which cannot be divided further as they have only*

**2***character left in them.*

**1**So now we start merging the leaf nodes in an arbitrary order to form the parent node. Now, this parent node can also merge with his sibling in any order. We can get multiple permutations of the original string using this algorithm.

** ***2. *** S1 = “ACTOR“**

**S2 = “RCATO”**

In this case, string** S2 **is not a scrambled form of **S1 **as** R **and **C **being adjacent is not possible.

Having understood the problem, move ahead to * Coding Ninjas Studio* and first try solving the

__problem__on your own.

Now, let us solve this problem using *basic recursion*, and then we will optimize our solution with the help of *dynamic programming. *