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 i,
Two things are possible,
So, we can formulate the problem recursively,
Now find the minimum.
The base value of f(i)=i obviously which is maximum value to form the string.
So, the above recursion can be transformed to DP.
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer