#B4139. Minimum Cost String Transformation

    ID: 11796 Type: Default 1000ms 256MiB

Minimum Cost String Transformation

Minimum Cost String Transformation

You are given two strings of equal length. You can perform the following two operations on the first string:

  1. Replace any character with any other character at a cost of \(1\).
  2. Swap any two characters in the string at a cost of \(0\).

Using a sequence of these operations, you can transform the first string into any other string of the same length. Your task is to compute the minimum cost required to convert the first string into the second string.

Note: Since swapping is free, you can rearrange the characters arbitrarily. The only cost incurred is when you need to replace a character when there is a mismatch in the frequency of characters between the two strings.

The minimum cost is given by:

\[ \text{cost} = n - \sum_{c} \min(\text{freq}_{s}(c), \text{freq}_{t}(c)) \]

where \(n\) is the length of the strings, and \(\text{freq}_{s}(c)\) (resp. \(\text{freq}_{t}(c)\)) indicates the frequency of character \(c\) in the first (resp. second) string.

inputFormat

The input consists of two lines. The first line contains the source string and the second line contains the target string, both having the same length.

outputFormat

Output a single integer: the minimum cost required to transform the source string into the target string.

sample

hello
world
3