All submissions for this problem are available.
Run-length 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.
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 [a-z] 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.
For each test case, output the edit distance from S1 to S2 in a new line.
Input: 2 2 a3b2 1 b3 3 a1b1a1 1 a2 Output: 7 2
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.