Minimum Adjustments for Choir Formation

A choir teacher is interested in adjusting the formation of the choir with minimum operations. The current formation and the target formation are given as strings, where each character represents the color of a person's clothing.

You are allowed to perform the following operations with a cost of 1 each:

• Add a person to the left end or right end of the formation.
• Insert a person between any two people in the formation.
• Remove a person from the formation.
• Change the clothing color of a person.

Assuming there is an infinite supply of people in any color, determine the minimum number of adjustments required to transform the current formation into the target formation.

This problem reduces to computing the Levenshtein edit distance between the two strings, with each allowed operation having a cost of 1.

All formulas are given in LaTeX format. For example, the recurrence for the edit distance \(d(i,j)\) is:

\[ d(i,j)=\min\begin{cases} d(i-1,j)+1,\\ d(i,j-1)+1,\\ d(i-1,j-1)+\left[\text{if } S[i] \neq T[j] \text{ then } 1 \text{ else } 0\right] \end{cases} \]

inputFormat

The input consists of two lines:

1. The first line is a non-empty string representing the current choir formation.
2. The second line is a non-empty string representing the target choir formation.

Each character in the string indicates the color of a person's clothing.

outputFormat

Output a single integer: the minimum number of adjustments required to transform the current formation into the target formation.

sample

RGB
RBG

2