Minimum cost to make two words equal P24879


Statement
 

pdf   zip

thehtml

We are given two words s and t made up of only lowercase letters, and we must make them equal. We can only perform two kind of operations, as many times as needed: Remove a letter, with cost 3, and duplicate a letter, with cost 2. What is the minimum possible cost?

For example, for s= “aaba” and t= “abb” the minimum cost is 7, which corresponds to duplicating the ‘b’ and removing the last ‘a’ of s, and duplicating the ‘a’ of t.

Input

Input consists of several cases with s and t, both with between 1 and 1000 letters.

Output

For every case, print the minimum cost to make the two words equal.

Public test cases
  • Input

    a a
    a b
    a aa
    aaba abb
    xxxxzz zxxxx
    g ggggggg
    

    Output

    0
    6
    2
    7
    9
    12
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++