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

19 June 2025

0

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

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:

dp[i] = min(dp[i], dp[i-1] + 1) which signifies addition of characters.
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]

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 the above idea:

C++

// CPP program to print the
// Minimal moves to form a string
// by appending string and adding characters
#include <bits/stdc++.h>
using namespace std;
 
// function 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[0] = 1;
 
    s1 += s[0];
 
    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 stored 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();
 
    // function 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
{
 
// function 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 stored 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();
 
    // function 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
 
# function 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 stored 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
{
 
// function 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[0] = 1;
 
    s1 += s[0];
 
    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 stored 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;
 
    // function call to return minimal number of moves
    Console.Write(minimalSteps(s, n)/2);
}
}
 
// This code has been contributed by 29AjayKumar

PHP

<?php
// php program to print the
// Minimal moves to form a 
// string by appending string
// and adding characters
 
// function to return the
// minimal number of moves
function minimalSteps($s,$n)
{
 
    // initializing dp[i] to INT_MAX
    for ($i = 0; $i < $n; $i++)
        $dp[$i] = PHP_INT_MAX;
 
    // initialize both 
    // strings to null
    $s1 = "";
    $s2 = "";
     
    // base case
    $dp[0] = 1;
 
    $s1=$s1.$s[0];
 
    for ($i = 1; $i < $n; $i++) 
    {
        $s1 = $s1.$s[$i];
 
        // check if it can 
        // be appended
        $s2 = substr($s, $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 stored 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 = strlen($s);
 
    // function call to return
    //minimal number of moves
    echo minimalSteps($s, $n);
 
// This code is contributed by mits 
?>

Javascript

// Javascript program to print the
// Minimal moves to form a string
// by appending string and adding characters
 
// function to return the minimal number of moves
function minimalSteps(s, n)
{
    let dp = [n]
 
    // initializing dp[i] to INT_MAX
    for (let i = 0; i < n; i++)
        dp[i] = Number.MAX_SAFE_INTEGER
 
    // initialize both strings to null
    let s1 = ""
    let s2 = ""
     
    // base case
    dp[0] = 1
 
    s1 += s[0]
 
    for (let 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] = 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 stored 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
let s = "aaaaaaaa"
let n = s.length
 
// function call to return minimal number of moves
console.log(minimalSteps(s, n))
 
// This code is contributed by Samim Hossain Mondal.

Output

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

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

C++

Java

Python3

C#

PHP

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US