Connection Status:
Competition Arena > EllysString

EllysString

SRM 534 · 2011-11-22 · by rng_58

SRM 534 · 2011-11-22 · by rng_58 · Dynamic Programming, String Manipulation
Class Name: EllysString
Return Type: int
Method Name: theMin
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

Elly has a string S. She wants to convert it to her favorite string T. You are given two String[]s s and t. Concatenate all elements of s to get the string S. Concatenate all elements of t to get the string T. S and T will contain the same number of characters.

Elly can perform two types of operations:
  • Choose a character and replace it with another character. For example, she can change "topcoder" to "topcodfr" by replacing character 6 (0-based index) with 'f'.
  • Choose two adjacent letters and swap them. For example, she can change "topcoder" to "tocpoder" by swapping characters 2 and 3 (0-based indices). She cannot change "topcoder" to "topdocer" because the characters being swapped must be adjacent.
Return the minimal number of operations required to convert S to T.

Constraints

  • s and t will contain between 1 and 50 elements, inclusive.
  • Each element of s and t will contain between 1 and 50 characters, inclusive.
  • Each character in s and t will be a lowercase letter ('a'-'z').
  • s and t will contain the same number of characters when concatenated.
Examples
0)
{"usagi"}
{"unagi"}
Returns: 1

Replace character 1 with 'n'.

1)
{"unagi"}
{"nugai"}
Returns: 2

In the first operation, swap characters 0 and 1 to get "nuagi". In the second operation, swap characters 2 and 3 to get "nugai".

2)
{"ellys", "string"}
{"e", "ll", "ysst", "ring"}
Returns: 0

Don't forget to concatenate strings. Both S and T are "ellysstring", so no operation is required.

3)
{"ackwgkbskceehauirbgkagkshiuafdkv"}
{"bckwgksbkceeahlirgbkamkshiaufkdv"}
Returns: 8
4)
{"abcdefghijklmnopqrstuvwxyz"}
{"bcdefghijklmnopqrstuvwxyza"}
Returns: 25
7)
{"fox"}
{"xfo"}
Returns: 2

In the first operation, swap characters 1 and 2 to get "fxo". In the second operation, swap characters 0 and 1 to get "xfo".

8)
{"salmon"}
{"camlon"}
Returns: 2

In the first operation, replace character 0 with 'c' to get "calmon". In the second operation, swap characters 2 and 3 to get "camlon".

9)
{"abcdxyefghzijklmnopv", "abcdxyefghzijklmnopv", "abcdxyefghzijklmnopv", "abcdxyefghzijklmnopv", "abcdxyefghzijklmnopv"}
{"xabcdefghyijklzvmnop", "xabcdefghyijklzvmnop", "xabcdefghyijklzvmnop", "xabcdefghyijklzvmnop", "xabcdefghyijklzvmnop"}
Returns: 80

This fails my first solution (espr1t)

10)
{"xyab"}
{"axby"}
Returns: 3

This fails my second solution (espr1t).

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

Coding Area

Language: C++17 · define a public class EllysString with a public method int theMin(vector<string> s, vector<string> t) · 177 test cases · 2 s / 256 MB per case

Submitting as anonymous