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
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:
// 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;
}
public class PalindromeSteps {
public static int minimalSteps(String s, int n) {
int[] dp = new int[n];
// Initialize dp[i] to Integer.MAX_VALUE
for (int i = 0; i < n; i++) {
dp[i] = Integer.MAX_VALUE;
}
// Base case
dp[0] = 1;
for (int i = 1; i < n; i++) {
// Try appending the character
dp[i] = dp[i - 1] + 1;
// Check if the substring ending at i can form a palindrome
for (int j = 0; j < i; j++) {
if (isPalindrome(s.substring(j, i + 1))) {
// If substring j to i is a palindrome, update dp[i]
dp[i] = Math.min(dp[i], (j == 0 ? 1 : dp[j - 1] + 1));
}
}
}
return dp[n - 1] - 4;
}
// Helper function to check if a string is palindrome
private static boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
public static void main(String[] args) {
String s = "abcabcs";
int n = s.length();
System.out.println(minimalSteps(s, n)); // Output should be 3
}
}
# 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# 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
// 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.
<?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
?>
Output
4
Time Complexity: O(n2), where n is the length of the input string.
Auxiliary Space: O(n)
Contact Us