Turning A into B

Interview

Time limit2sMemory limit512 MB

Summary

Given two equal-length uppercase strings A and B, find the minimum number of moves that bring a chosen character to the front of A so that A becomes B, or -1 if impossible.

Level: Medium5 of 10
Topics: String, Greedy, Two pointers, Hash map
Solved: No attempts yet

Problem

You are given two strings A and B. One operation picks a single character of A and moves it to the very front of the string.

Write a program that computes the minimum number of operations needed to turn A into B.

Input

The first line contains A and the second line contains B. The two strings have the same length, which is at most 50, and both consist of uppercase letters only.

Output

Print the minimum number of operations that turns A into B. If A cannot be turned into B, print -1.

Examples5

Example 1
Input
```
ABC
CBA
```
Expected output
```
2
```
Example 2
Input
```
A
B
```
Expected output
```
-1
```
Example 3
Input
```
AAABBB
BBBAAA
```
Expected output
```
3
```
Example 4
Input
```
A
A
```
Expected output
```
0
```
Example 5
Input
```
DCABA
DACBA
```
Expected output
```
2
```