Minimal moves to form a string

Minimal moves to form a string: In this article, we are going to see a standard interview problem and its solution which can be featured in any company interview process.
Submitted by Radib Kar, on June 09, 2020

Problem statement:

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:

  1. Add any character at the end of the string.
  2. 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"

Solution Approach:

So, we have two option

  1. Append single character
  2. Append the string itself

So, say the string is

x1x2 ... xn

For any sub-problem of size i,

x1x2 ... xi

Two things are possible,

  1. Appends xi to sub-problem x1x2 ... x(i-1)
  2. Append x1..xj to x1..xj is x(j+1)..xi is similar to x1..xj

So, we can formulate the problem recursively,

f(i) = minimum steps to form x1x2 ... xi  
f(i) = f(i-1)+1
f(i) = f(j)+1 if j=i/2 and the partitioned strings are same 

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.

1)  Declare int dp[n+1];
2)  Assign the base value.    
    for i=0 to n
        dp[i]=i;
3)  Fill the DP array
    for i=2 to n
        dp[i]=minimum(dp[i-1]+1,dp[i]); // normal insertion, recursion first case
        if i is even
            if s1s(i/2) = s(i/2+1)sn // if appending string is possible
                dp[i]=minimum(dp[i],dp[i/2]+1);
        end if
    end for
    
4)  return dp[n];

DP[n] is the final result

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int minimumMoves(string s)
{
    int n = s.length();

    int dp[n + 1];
    for (int i = 0; i <= n; i++)
        dp[i] = i;

    for (int i = 2; i <= n; i++) {
        dp[i] = std::min(dp[i - 1] + 1, dp[i]);
        if (i % 2 == 0) {
            int flag = 0;
            for (int j = 0; j < i / 2; j++) {
                if (s[j] != s[j + i / 2]) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0)
                dp[i] = std::min(dp[i], dp[i / 2] + 1);
        }
    }

    return dp[n];
}

int main()
{
    cout << "Enter input string\n";
    string s;
    cin >> s;
    
    cout << "Minimum steps to form te string: " << minimumMoves(s) << endl;

    return 0;
}

Output:

Enter input string
incinclude
Minimum steps to form te string: 8





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.