Edit Distance

All submissions for this problem are available.
Runlength encoding(RLE) is a very simple and easy form of data compression in which consecutive occurrences of the same characters are replaced by a single character followed by its frequency. As an example, the string S aabbbbdaa would be encoded to a2b4d1a2.
Thus encoded string is described as an ordered sequence of pairs (a, i), each consisting of an alphabet symbol a and an integer i. Each pair corresponds to a run in S consisting of i consecutive occurrences of a.
In this problem, we are interested in finding the minimum number of mutation(s) needed to transform first string given in encoded form into second string i.e. edit distance when only two operation are allowed
 Add any character at any position(insertion)
 Remove any character from any position(deletion)
The cost of inserting a character is 1 and cost of deleting a character is 2.
Input
The input file contains several test cases. The first line of the input denotes the number of test cases, T (1≤T≤100) to follow. Each test case begins on a new line and consists of an integer L1, a blankspace and a run length encoded string S1 and then on a new line, an integer L2, a blankspace and a run length encoded string S2.
L1 and L2 denote the number of runs in strings S1 and S2 respectively. 1<=L1,L2<=100.
S1 and S2 consists of alphabets [az] followed by number of consecutive occurrences of that character.
You can safely assume that the total length of any of the strings will not exceed 3000 characters.
Output
For each test case, output the edit distance from S1 to S2 in a new line.
Example
Input: 2 2 a3b2 1 b3 3 a1b1a1 1 a2 Output: 7 2
Author:  manthan 
Tags  manthan 
Date Added:  26032010 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, PYTH 3.6, PYPY, GO, NODEJS, rust, swift, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 