SRM597 IIM, IE

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12854

概要

n文字の文字列A, Bが与えられている．
文字列Aの任意の文字を先頭に回すことができる．
AとBの文字列を一致させるために必要な最小の上記の操作回数を教えてください．
解が存在しない場合は-1を返す．

制約条件

• 1 <= n <= 50
• |A| = |B|
• 'A' <= A[i] <= 'Z' (for i = 0, 1, 2, ..., n-1)
• 'A' <= B[i] <= 'Z' (for i = 0, 1, 2, ..., n-1)

解法

任意のタイミングで先頭に文字を回すことができるので，
対象の文字に対して必要な操作の回数はたかだか1回となる．

コード

class LittleElephantAndString {
public:
	bool isImpossible(string A, string B) {
		sort(A.begin(), A.end());
		sort(B.begin(), B.end());
		return (A != B);
	}

	int getNumber(string A, string B) {
		if (this->isImpossible(A, B)) return -1;
		int n = A.size();
		int j = n - 1;
		for (int i = n - 1; i >= 0; --i)
			if (A[i] == B[j])
				--j;
		return j + 1;
	}
}