Connection Status:
Competition Arena > LittleElephantAndString

LittleElephantAndString

SRM 597 · 2013-06-25 · by Witaliy

SRM 597 · 2013-06-25 · by Witaliy · Brute Force
Class Name: LittleElephantAndString
Return Type: int
Method Name: getNumber
Arg Types: (string, string)
Problem Statement

Problem Statement

Little Elephant from the Zoo of Lviv likes strings.

You are given a String A and a String B of the same length. In one turn Little Elephant can choose any character of A and move it to the beginning of the string (i.e., before the first character of A). Return the minimal number of turns needed to transform A into B. If it's impossible, return -1 instead.

Constraints

  • A will contain between 1 and 50 characters, inclusive.
  • B will contain between 1 and 50 characters, inclusive.
  • A and B will be of the same length.
  • A and B will consist of uppercase letters ('A'-'Z') only.
Examples
0)
"ABC"
"CBA"
Returns: 2

The optimal solution is to make two turns. On the first turn, choose character 'B' and obtain string "BAC". On the second turn, choose character 'C' and obtain "CBA".

1)
"A"
"B"
Returns: -1

In this case, it's impossible to transform A into B.

2)
"AAABBB"
"BBBAAA"
Returns: 3
3)
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"ZYXWVUTSRQPONMLKJIHGFEDCBA"
Returns: 25
4)
"A"
"A"
Returns: 0

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

Coding Area

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

Submitting as anonymous