• Tweet

• Tweet

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 S_i ≠ S_i+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

Subtasks

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[0];
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[0];
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
        {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int t = Integer.parseInt(br.readLine());
            while(t-- >0) {
                StringTokenizer str = new StringTokenizer(br.readLine()," ");
                int n = Integer.parseInt(str.nextToken());
                int m = Integer.parseInt(str.nextToken());
                String a = br.readLine();
                String b = br.readLine();
                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<n-1; i++)
                {
                    ch1=a.charAt(i);
                    ch2=a.charAt(i+1);
                    if(ch1!=ch2)
                    {
                        aAfterRemDupChar = aAfterRemDupChar + ch2;
                        nAfterRemDupChar++;
                    }
                }

                for(int i=0; i<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][0]=0;

                for(int i=1 ; i < nAfterRemDupChar+1 ; i++)
                {
                            dp[0][i] =dp[0][i-1] +1;

                }

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

                for(int i=1 ; i < mAfterRemDupChar+1 ; i++)
                {
                    for(int j=1 ; j < 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 < mAfterRemDupChar+1 ; i++)
                {
                    for(int j=0 ; j < 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.