# Minimal moves to form a string

Given a string **S**, write a program to check if it is possible to construct the given string **S** by performing any of the below operations any number of times. In each step, you can:

- Add any character at the end of the string.
- Append the existing string to the string itself.

The above steps can be applied any number of times. We need to print the minimum steps required to form the string.

**Input:**

Input String

**Output:**

Minimum number of steps required to form that string.

**Constraints:**

1 <= string length <= 10^5

**Example:**

Input:
aaaaaaaa
Output:
4
Explanation:
Move 1: add 'a' to form "a"
Move 2: add 'a' to form "aa"
Move 3: append "aa" to form "aaaa"
Move 4: append "aaaa" to form "aaaaaaaa"
Input:
ijhijhi
Output:
5
Explanation:
Move 1: add 'i' to form "i"
Move 2: add 'j' to form "ij"
Move 3: add 'h' to form "ijh"
Move 4: append "ijh" to form "ijhijh"
Move 5: add 'i' to form "ijhijhi"

So, we have two option

So, say the string is

For any sub-problem of size

,iTwo things are possible,

So, we can formulate the problem recursively,

Now find the minimum.

The base value of

f(i)=iobviously which is maximum value to form the string.So, the above recursion can be transformed to DP.

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: