# Minimal moves to form a string by adding characters or appending string itself

Given a string S, we need to 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, we can:

• Add any character at the end of the string.
• or, append the string to the string itself.

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

Examples:

```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: aaaaaa
Output: 4
Explanation: move 1: add 'a' to form "a"
move 2: add 'a' to form "aa"
move 3: add 'a' to form "aaa"
move 4: append "aaa" to form "aaaaaa"

Input: abcabca
Output: 5
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea to solve this problem is to use Dynamic Programming to count the minimum number of moves. Create an array named dp of size n, where n is the length of the input string. dp[i] stores the minimum number of moves that are required to make substring (0…i). According to the question there are two moves that are possible:

1. dp[i] = min(dp[i], dp[i-1] + 1) which signifies addition of characters.
2. dp[i*2+1] = min(dp[i]+1, dp[i*2+1]), appending of string is done if s[0…i]==s[i+1..i*2+1]
3. The answer will be stored in dp[n-1] as we need to form the string(0..n-1) index-wise.

Below is the implementation of above idea:

## C++

 `// CPP program to print the ` `// Minimal moves to form a string ` `// by appending string and adding characters ` `#include ` `using` `namespace` `std; ` ` `  `// fucntion to return the minimal number of moves ` `int` `minimalSteps(string s, ``int` `n) ` `{ ` ` `  `    ``int` `dp[n]; ` ` `  `    ``// initializing dp[i] to INT_MAX ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``dp[i] = INT_MAX; ` ` `  `    ``// initialize both strings to null ` `    ``string s1 = ``""``, s2 = ``""``; ` `     `  `    ``// base case ` `    ``dp = 1; ` ` `  `    ``s1 += s; ` ` `  `    ``for` `(``int` `i = 1; i < n; i++) { ` `        ``s1 += s[i]; ` ` `  `        ``// check if it can be appended ` `        ``s2 = s.substr(i + 1, i + 1); ` ` `  `        ``// addition of character takes one step ` `        ``dp[i] = min(dp[i], dp[i - 1] + 1); ` ` `  `        ``// appending takes 1 step, and we directly ` `        ``// reach index i*2+1 after appending ` `        ``// so the number of steps is stord in i*2+1 ` `        ``if` `(s1 == s2) ` `            ``dp[i * 2 + 1] = min(dp[i] + 1, dp[i * 2 + 1]); ` `    ``} ` ` `  `    ``return` `dp[n - 1]; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` ` `  `    ``string s = ``"aaaaaaaa"``; ` `    ``int` `n = s.length(); ` ` `  `    ``// fucntion call to return minimal number of moves ` `    ``cout << minimalSteps(s, n); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to print the ` `// Minimal moves to form a string ` `// by appending string and adding characters ` `import` `java.util.*; ` ` `  `class` `GFG ` `{ ` ` `  `// fucntion to return the minimal number of moves ` `static` `int` `minimalSteps(String s, ``int` `n) ` `{ ` ` `  `    ``int` `[]dp = ``new` `int``[n]; ` `     `  `    ``// initializing dp[i] to INT_MAX ` `    ``for` `(``int` `i = ``0``; i < n; i++) ` `        ``dp[i] = Integer.MAX_VALUE; ` ` `  `    ``// initialize both strings to null ` `    ``String s1 = ``""``, s2 = ``""``; ` `     `  `    ``// base case ` `    ``dp[``0``] = ``1``; ` ` `  `    ``s1 += s.charAt(``0``); ` ` `  `    ``for` `(``int` `i = ``1``; i < n; i++) ` `    ``{ ` `        ``s1 += s.charAt(i); ` ` `  `        ``// check if it can be appended ` `        ``s2 = s.substring(i + ``1``, i + ``1``); ` ` `  `        ``// addition of character takes one step ` `        ``dp[i] = Math.min(dp[i], dp[i - ``1``] + ``1``); ` ` `  `        ``// appending takes 1 step, and we directly ` `        ``// reach index i*2+1 after appending ` `        ``// so the number of steps is stord in i*2+1 ` `        ``if` `(s1 == s2) ` `            ``dp[i * ``2` `+ ``1``] = Math.min(dp[i] + ``1``,  ` `                                   ``dp[i * ``2` `+ ``1``]); ` `    ``} ` `    ``return` `dp[n - ``1``]; ` `} ` ` `  `// Driver Code ` `public` `static` `void` `main(String args[]) ` `{ ` ` `  `    ``String s = ``"aaaaaaaa"``; ` `    ``int` `n = s.length(); ` ` `  `    ``// fucntion call to return minimal number of moves ` `    ``System.out.println(minimalSteps(s, n)/``2``); ` `} ` `} ` ` `  `// This code is contributed by  ` `// Shashank_Sharma `

## Python3

 `# Python program to print the  ` `# Minimal moves to form a string  ` `# by appending string and adding characters  ` ` `  `INT_MAX ``=` `100000000` ` `  `# fucntion to return the  ` `# minimal number of moves  ` `def` `minimalSteps(s, n): ` `    ``dp ``=` `[INT_MAX ``for` `i ``in` `range``(n)]  ` `     `  `    ``# initialize both strings to null  ` `    ``s1 ``=` `"" ` `    ``s2 ``=` `"" ` `     `  `    ``# base case  ` `    ``dp[``0``] ``=` `1` `    ``s1 ``+``=` `s[``0``] ` `     `  `    ``for` `i ``in` `range``(``1``, n): ` `        ``s1 ``+``=` `s[i] ` `     `  `        ``# check if it can be appended  ` `        ``s2 ``=` `s[i ``+` `1``: i ``+` `1` `+` `i ``+` `1``] ` `     `  `        ``# addition of character  ` `        ``# takes one step  ` `        ``dp[i] ``=` `min``(dp[i], dp[i ``-` `1``] ``+` `1``) ` `     `  `        ``# appending takes 1 step, and  ` `        ``# we directly reach index i*2+1  ` `        ``# after appending so the number ` `        ``# of steps is stord in i*2+1  ` `        ``if` `(s1 ``=``=` `s2):  ` `            ``dp[i ``*` `2` `+` `1``] ``=` `min``(dp[i] ``+` `1``,  ` `                                ``dp[i ``*` `2` `+` `1``]) ` `     `  `    ``return` `dp[n ``-` `1``] ` ` `  `# Driver Code  ` `s ``=` `"aaaaaaaa"` `n ``=``len``(s) ` ` `  `# function call to return  ` `# minimal number of moves  ` `print``( minimalSteps(s, n) )  ` ` `  `# This code is contributed  ` `# by sahilshelangia `

## C#

 `// C# program to print the ` `// Minimal moves to form a string ` `// by appending string and adding characters ` `using` `System; ` `     `  `class` `GFG ` `{ ` ` `  `// fucntion to return the minimal number of moves ` `static` `int` `minimalSteps(String s, ``int` `n) ` `{ ` ` `  `    ``int` `[]dp = ``new` `int``[n]; ` `     `  `    ``// initializing dp[i] to INT_MAX ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``dp[i] = ``int``.MaxValue; ` ` `  `    ``// initialize both strings to null ` `    ``String s1 = ``""``, s2 = ``""``; ` `     `  `    ``// base case ` `    ``dp = 1; ` ` `  `    ``s1 += s; ` ` `  `    ``for` `(``int` `i = 1; i < n; i++) ` `    ``{ ` `        ``s1 += s[i]; ` ` `  `        ``// check if it can be appended ` `        ``s2 = s.Substring(i , 1); ` ` `  `        ``// addition of character takes one step ` `        ``dp[i] = Math.Min(dp[i], dp[i - 1] + 1); ` ` `  `        ``// appending takes 1 step, and we directly ` `        ``// reach index i*2+1 after appending ` `        ``// so the number of steps is stord in i*2+1 ` `        ``if` `(s1 == s2) ` `            ``dp[i * 2 + 1] = Math.Min(dp[i] + 1,  ` `                                ``dp[i * 2 + 1]); ` `    ``} ` `    ``return` `dp[n - 1]; ` `} ` ` `  `// Driver Code ` `public` `static` `void` `Main(String []args) ` `{ ` ` `  `    ``String s = ``"aaaaaaaa"``; ` `    ``int` `n = s.Length; ` ` `  `    ``// fucntion call to return minimal number of moves ` `    ``Console.Write(minimalSteps(s, n)/2); ` `} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

## PHP

 ` `

Output:

```4
```

Time Complexity : O(n2), where n is the length of input string.