[10453] 문자열 변환

문제

두 문자열 A와 B 가 주어질 때 좋은 문자열을 유지하며 A에서 B로 아래의 규칙을 따르며 변환할 수 있을까?

좋은 문자열의 규칙
1. ab 는 좋은 문자열이다.
2. 만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다.
3. 만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다.

변환 규칙은 간단하다. 인접한 두 문자만을 교환할 수 있다.
ex) aabb -> abab (O)
aabb -> baba (X)

문자열의 길이는 최대 10만이다.

Sol

A와 B 모두 좋은 문자열임이 확신되어 있고 규칙 상 A와 B의 부분 문자열들 또한 좋은 문자열을 유지해 어떻게 변환해도 좋은 문자열을 유지할 것이라 생각해 A와 B의 다른 부분만 찾아 스왑하고 그 때 변환한 카운트를 세어주었다.

solution code

void sol(){
    int cnt = 0;
    cin >> s >> d;
    vector<int>da, db;

    for(int i=0; s[i]!='\0'; i++){
        if(s[i] == d[i])continue;
        if(s[i] == 'a')da.push_back(i);
        else db.push_back(i);
    }
    if(da.size()!=db.size()){
        cout << -1 << '\n';
        return;
    }
    for(int i=0; i<min(da.size(),db.size()); i++){
        cnt += abs(da[i]-db[i]);
    }

    cout << cnt <<'\n';
}