-
Notifications
You must be signed in to change notification settings - Fork 1
/
minimal moves to form a string.cpp
42 lines (42 loc) · 1.21 KB
/
minimal moves to form a string.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//problem link: https://practice.geeksforgeeks.org/problems/minimal-moves-to-form-a-string/0
#include<bits/stdc++.h>
using namespace std;
bool check(int i,string str)
{
string str1, str2;
for(int j=0;j<=i/2;j++)
str1.push_back(str[j]);
for(int j=i/2+1;j<=i;j++)
str2.push_back(str[j]);
if(str1==str2)
return true;
else
return false;
}
int main()
{
int t;
cin>>t;
while(t--)
{
string str;
cin>>str;
int n=str.length();
int dp[n+1]={0};
for(int i=0;i<n;i++)
{
/*USE OF DP: In 1D array, we store the minimal no. of moves for ith index
like in abcabca, minimal no. of moves at 0th index is 1 , 1st index is 2 & so on.*/
//HERE DP COMES INTO PLAY: at 5th index of abcabca we require 4 moves,
//i.e. no. of moves of dp[i/2]+1 as abc itself is entered again before
//checking the condition that string from 0 to i/2 & i/2 +1 to i are equal
if (check(i,str)==true)
dp[i]=dp[i/2]+1;
else
dp[i]=dp[i-1]+1;
}
cout<<dp[n-1]<<endl;
}
//code
return 0;
}