# String Merging Codechef January Challenge

For a string S, let’s define a function F(S) as the minimum number of blocks consisting of consecutive identical characters in S. In other words, F(S) is equal to 1 plus the number of valid indices i such that SiSi+1.

You are given two strings A and B with lengths N and M respectively. You should merge these two strings into one string C with length N+M. Specifically, each character of C should come either from A or B; all characters from A should be in the same relative order in C as in A and all characters from B should be in the same relative order in C as in B.

Compute the minimum possible value of F(C).

### Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two space-separated integers N and M.
• The second line contains a single string A with length N.
• The third line contains a single string B with length M.

### Output

For each test case, print a single line containing one integer — the minimum possible value of F(C).

### Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N, M ≤ 5,000
• 1 ≤ sum of N in all test cases ≤ 5,000
• 1 ≤ sum of M in all test cases ≤ 5,000
• strings A, B consist only of lowercase English letters

Subtask 1 (10 points): 1 ≤ T, N, M ≤ 10

Subtask 2 (20 points): the characters of A and B are sorted in non-decreasing order

Subtask 3 (70 points): original constraints

### Example

```<b>Input:</b>

1
4 4
abab
baba

<b>Output:</b>

5
```

### Explanation

Example case 1: One possible way to choose the string C to get the desired answer is “abbaabba”

## TLE C++ Solution:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define INT_MAX 999999

using namespace std;
//ABBAABBA
void printIlsRecur (char *str1, char *str2, char *iStr, int m,
int n, int i, int count,int &min)
{
if (m==0 && n==0)
{
//cout << “Outside:” << count << ” \t” << iStr << “\n”;
if(count < min)
{
//cout << count << ” \t” << iStr << “\n”;
min=count;
}
}

if (m != 0)
{
iStr[i] = str1;
if(i>0 && iStr[i] != iStr[i-1])
count++;
if(count >= min)
return;
printIlsRecur (str1 + 1, str2, iStr, m-1, n, i+1,count,min);
if(i>0 && iStr[i] != iStr[i-1])
count–;
}
//count–;
if (n != 0)
{
iStr[i] = str2;
if(i > 0 && iStr[i] != iStr[i-1])
count++;
if(count >=min)
return;
printIlsRecur(str1, str2+1, iStr, m, n-1, i+1,count,min);
}
//count–;
}

void printIls (char *str1, char *str2, int m, int n)
{
char *iStr= (char*)malloc((m+n+1)*sizeof(char));

iStr[m+n] = ‘\0’;
int count =1,min=INT_MAX;
printIlsRecur (str1, str2, iStr, m, n, 0,count,min);
cout << min<<endl;
free(iStr);
}

int main()
{
//char str1[] = “ABAB”;
//char str2[] = “BABA”;
int t=0;
cin >> t;
for(int i=0 ; i < t ; i++)
{
int m ,n;
cin >> m >> n;
char str1[m],str2[n];
//str1 = (char*)malloc((m)*sizeof(char));
//str2 = (char*)malloc((n)*sizeof(char));
for(int i =0 ; i <m ; i++)
cin >> str1[i];
for(int i =0 ; i <n ; i++)
cin>> str2[i];
printIls (str1, str2, m, n);
}
return 0;
}

## WA – Java Solution (70 Marks out of 100) – Solved with Dynamic programming ( DP)

```import java.io.*;
import java.util.StringTokenizer;

import static java.lang.Integer.min;

/**
* Created by tarun on 1/9/18.
*/

public  class STRMRG
{

public static void main(String[] args) throws IOException
{
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while(t-- &gt;0) {
StringTokenizer str = new StringTokenizer(br.readLine()," ");
int n = Integer.parseInt(str.nextToken());
int m = Integer.parseInt(str.nextToken());
char ch1,ch2;
String aAfterRemDupChar ="";
String bAfterRemDupChar ="";
int nAfterRemDupChar=1,mAfterRemDupChar=1;

aAfterRemDupChar = aAfterRemDupChar + a.charAt(0);
bAfterRemDupChar = bAfterRemDupChar + b.charAt(0);
for(int i=0; i&lt;n-1; i++)
{
ch1=a.charAt(i);
ch2=a.charAt(i+1);
if(ch1!=ch2)
{
aAfterRemDupChar = aAfterRemDupChar + ch2;
nAfterRemDupChar++;
}
}

for(int i=0; i&lt;m-1; i++)
{
ch1=b.charAt(i);
ch2=b.charAt(i+1);
if(ch1!=ch2)
{
bAfterRemDupChar = bAfterRemDupChar + ch2;
mAfterRemDupChar++;
}
}

int[][] dp = new int[mAfterRemDupChar+1][nAfterRemDupChar+1];

dp=0;

for(int i=1 ; i &lt; nAfterRemDupChar+1 ; i++)
{
dp[i] =dp[i-1] +1;

}

for(int i=1 ; i &lt; mAfterRemDupChar+1 ; i++)
{
dp[i] =dp[i-1] +1;
}

for(int i=1 ; i &lt; mAfterRemDupChar+1 ; i++)
{
for(int j=1 ; j &lt; nAfterRemDupChar+1 ; j++) {

if(bAfterRemDupChar.charAt(i-1) == aAfterRemDupChar.charAt(j-1))
{
dp[i][j] = dp[i-1][j-1]+1;
}
else
{
dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1;
}
}
}

for(int i=0 ; i &lt; mAfterRemDupChar+1 ; i++)
{
for(int j=0 ; j &lt; nAfterRemDupChar+1 ; j++) {

System.out.print(dp[i][j] + "\t");
}

System.out.print("\n");

}
bw.write("" + dp[mAfterRemDupChar][nAfterRemDupChar]);
bw.flush();
}
}
}```

please let me know mistaked missed cases to get 100 points in above code.