## Mock CCC '22 Contest 1 J3 - String Crossing Maximization

View as PDF

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem type

We're given two strings, and , containing only uppercase English characters (ABCDEFGHIJKLMNOPQRSTUVWXYZ).

If a character at index of string is the same as the character at index of string , the two strings may cross at those indices. We define this as a string crossing.

Here is a visual example of a string crossing:

    G
O
HELLOWORLD
D
B
Y
E

You are allowed to modify up to one character in string by changing the character at any index to another uppercase English character.

Your job is to determine the maximum number of string crossings after modifying up to one character in string .

#### Constraints

For this problem, you will NOT be required to pass all the samples to receive points, and you are NOT required to pass all previous subtasks to receive points for a specific subtask.

represents the length of a string .

and will only contain the characters A and B.

#### Input Specification

The first line will contain and , space-separated.

The second line will contain .

The third and final line will contain .

#### Output Specification

Output one integer on one line, the maximum number of string crossings after modifying up to one character in string .

#### Sample Input

10 7
HELLOWORLD
GOODBYE

#### Sample Output

9

#### Explanation

Without any modifications, we can count string crossings.

If we change the Y in GOODBYE to an L, we can now count crossings.