Connection Status:
Competition Arena > ChangingString

ChangingString

SRM 341 · 2007-03-10 · by pure_

SRM 341 · 2007-03-10 · by pure_ · Brute Force, String Manipulation
Class Name: ChangingString
Return Type: int
Method Name: distance
Arg Types: (string, string, int)
Problem Statement

Problem Statement

You are given two Strings A and B that have the same length and contain only lowercase letters ('a'-'z'). The distance between two letters is defined as the absolute value of their difference. The distance between A and B is defined as the sum of the differences between each letter in A and the letter in B at the same position. For example, the distance between "abcd" and "bcda" is 6 (1 + 1 + 1 + 3).

You must change exactly K characters in A into other lowercase letters. Return the minimum possible distance between A and B after you perform that change.

Constraints

  • A and B will each contain between 1 and 50 characters, inclusive.
  • K will be between 1 and the length of A, inclusive.
  • A and B will contain the same number of characters.
  • A and B will contain only lowercase letters ('a' - 'z').
Examples
0)
"ab"
"ba"
2
Returns: 0

The minimum distance (equal to 0) can be achieved when we change 'a' to 'b' and 'b' to 'a'.

1)
"aa"
"aa"
2
Returns: 2

We must change both letters 'a' to some other letters. Changing them to 'b' results in the smallest distance.

2)
"aaa"
"baz"
1
Returns: 1
3)
"fdfdfdfdfdsfabasd"
"jhlakfjdklsakdjfk"
8
Returns: 24
4)
"aa"
"bb"
2
Returns: 0

Submissions are judged against all 101 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ChangingString with a public method int distance(string A, string B, int K) · 101 test cases · 2 s / 256 MB per case

Submitting as anonymous