文字列の長さを \(N\)、\(S_i \neq T_i\) なる \(i\) の個数を \(x\) とおきます。

答えの要素数、すなわち操作回数として考えられる最小の値は \(x\) であり、すべての操作は \(S_i \neq T_i\) である \(i\) を選び \(S_i\) を \(T_i\) に書き換えるものとなることがわかります。

操作の順番を考えます。

\(S_i \neq T_i\) である \(i\) を選び \(S_i\) を \(T_i\) に書き換える操作は可換であることに注意すると、辞書順最小化のためにはそのような操作をすべて試し、操作後の文字列が辞書順最小となる操作を実際に行えばよいです。

本問題の制約下では上記の操作をそのまま繰り返せばよく、時間計算量は \(O(N^3)\) と評価できます。

また、高速化を行うこともできます。

\(S_i\) を \(T_i\) に書き換える操作では \(S_i < T_i\) のとき元の文字列より辞書順が大きく、\(S_i > T_i\) のとき元の文字列より辞書順が小さくなります。

したがって、\(S_i > T_i\) なる \(i\) が存在するならばそのような \(i\) に対して操作を行うのが最適であり、特に \(i\) として最小であるものを取るのが最適です。また、\(S_i > T_i\) なる \(i\) が存在しないときは \(S_i < T_i\) なる最大の \(i\) に対して操作を行うことが最適となります。

この操作を \(S \neq T\) である限り繰り返せばよく、時間計算量は \(O(N^2)\) と評価できます。

実装例 (\(O(N^3)\))

#include <bits/stdc++.h>
using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	vector<string> ans;
	int n = s.size();
	while (s != t) {
		string nxt(n, 'z');
		for (int i = 0; i < n; i++) {
			if (s[i] != t[i]) {
				string tmp = s;
				tmp[i] = t[i];
				nxt = min(nxt, tmp);
			}
		}
		ans.push_back(nxt);
		s = nxt;
	}
	int sz = ans.size();
	cout << sz << '\n';
	for (string e : ans) cout << e << '\n';
}

実装例 (\(O(N^2)\))

#include <bits/stdc++.h>
using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	vector<string> ans;
	vector<int> v;
	int n = s.size();
	for (int i = 0; i < n; i++) {
		if (s[i] > t[i]) v.push_back(i);
	}
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] < t[i]) v.push_back(i);
	}
	int sz = v.size();
	for (int i = 0; i < sz; i++) {
		s[v[i]] = t[v[i]];
		ans.push_back(s);
	}
	cout << sz << '\n';
	for (string e : ans) cout << e << '\n';
}