CONVSTR - Editorial


Contest: Division 1
Contest: Division 2

Setter: Vivek Chauhan
Tester: Radoslav Dimitrov
Editorialist: Taranpreet Singh




Greedy (slightly).


Given two strings A and B of length N, determine if we can convert string A to string B using following operation minimum number of times.

Each operation is defined as

  • Choose a non-empty subset of positions S.
  • Find minc = min(A_x) for all x \in S
  • Replace A_x = minc for all x \in S


  • In each operation, minc \leq A_x for all x \in S, so if we have A_x < B_x for any position x, there’s no possible way to convert string A to string B
  • Also, if there’s some character present in B not present in A, we cannot convert string A to string B.
  • In all other cases, it is possible to convert. Let’s consider all positions where A_x \neq B_x and among these, consider all B_x. The minimum number of operations needed is the number of distinct characters among these.
  • Consider all characters in this set in reverse order, and apply the operation on all positions having B_x same as the current character, and add one position where A_x is the same as current character.


Let’s figure out the impossible cases.

Firstly, we can see that each operation replaces A_x by some characters c where c \leq A_x. So, if for any position, we have A_x < B_x, we can never achieve that and thus, the answer becomes impossible.


aaa aab

Secondly, the operation replaces A_x by c where c is present in string A. Hence, if there’s any character in B not present in A, then the answer is impossible.


aac aab

We can prove that the answer is possible in every other case.

Another observation we need is that in each operation, all positions are updated to same character. So, if we consider all positions where B_x < A_x, the number of distinct characters among such B_x is the minimum number of operations since in each operation, we can group all such positions by B_x and apply operations.

For each operation grouped by ch = B_x, we choose those positions as subset for current operations. Additionally, to ensure min(A_x) = ch, we also need to add some position y in subset such that A_y = ch. Calling it special position for this operation.

Lastly, we need to decide the order of operations.


abc aab
Decide the order of operations.

Correct output

2 1 2
2 0 1

We can prove that it is optimal to apply operations in decreasing order of ch as it doesn’t affect candidate positions for special positions for subsequent operations.


The time complexity is O(A+N) where A = 26 is the size of the alphabet.


Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 200005;
char en = '\n';
ll inf = 2e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
	if (n & 1)
	  res = (res * x) % mod;
	x = (x * x) % mod;
	n >>= 1;
  return res;

void update(string &a, vector<ll> op) {
  char c = 'z';
  for (ll &x : op)
	c = min(c, a[x]);
  for (ll &x : op)
	a[x] = c;

vector<vector<ll>> res;
ll solve(string a, string b, ll n) {
  vector<int> indices[30];
  for (int i = 0; i < n; i++)
	indices[b[i] - 'a'].emplace_back(i);

  bool visited[n + 5];
  memset(visited, false, sizeof(visited));

  for (int i = 25; i >= 0; i--) {

	if (indices[i].empty())

	vector<ll> curr;

	for (ll j = 0; j < n; j++) {
	  if (!visited[j] && (a[j] - 'a') >= i)

	bool good = true;
	for (int &x : indices[i]) {
	  visited[x] = true;
	  if ((a[x] - 'a') != i) {
	    good = false;

	if (good)
	update(a, curr);


  if (a != b) {
	return -1;
  return res.size();
int32_t main() {

  ll t;
  cin >> t;

  while (t--) {
	ll n;
	cin >> n;
	string a, b;
	cin >> a >> b;

	ll val = solve(a, b, n);
	if (val == -1) {
	  cout << -1 << en;

	cout << res.size() << en;
	for (vector<ll> &x : res) {
	  cout << x.size() << " ";
	  for (ll &y : x)
	    cout << y << " ";
	  cout << en;
  return 0;
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back

using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int n;
string a;
string b;

void read() {
	cin >> n;
	cin >> a;
	cin >> b;

void solve() {
	vector<vector<int> > ans;
	for(int i = 0; i < n; i++) {
		if(a[i] < b[i]) {
			cout << -1 << endl;

	for(char c = 'z'; c >= 'a'; c--) {
		vector<int> pos;
		bool ok = 0;

		for(int i = 0; i < n; i++) {
			if(b[i] == c && a[i] != c) {

		if(!ok && !pos.empty()) {
			for(int i = 0; i < n; i++) {
				if(a[i] == c) {
					ok = 1;

		if(!ok && !pos.empty()) {
			cout << -1 << endl;

		if(!pos.empty()) ans.pb(pos);
		for(int i: pos) {
			a[i] = c;

	cout << SZ(ans) << endl;
	for(auto li: ans) {
		cout << SZ(li) << " ";
		for(int x: li) cout << x << " ";
		cout << endl;

int main() {

	int T;
	cin >> T;
	while(T--) {

	return 0;
Editorialist's Solution
import java.util.*;
import java.text.*;
class CONVSTR{
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni(), T = 26;
	    String A = n(), B = n();
	    ArrayList<Integer>[] op = new ArrayList[T];
	    for(int i = 0; i< T; i++)op[i] = new ArrayList<>();
	    boolean possible = true;
	    int[] pos = new int[T];
	    Arrays.fill(pos, -1);
	    for(int i = 0; i< N; i++){
	        pos[A.charAt(i)-'a'] = i;
	        if(A.charAt(i) != B.charAt(i)){
	            if(A.charAt(i) < B.charAt(i))possible = false;
	            else op[B.charAt(i)-'a'].add(i);
	    for(int i = 0; i< T; i++)if(!op[i].isEmpty() && pos[i] == -1)possible = false;
	        int ans = 0;
	        for(int i = 0; i< T; i++)if(!op[i].isEmpty())ans++;
	        for(int i = T-1; i >= 0; i--){
	            p(" "+pos[i]);
	            for(int x:op[i])p(" "+x);pn("");
	    }else pn(-1);
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	public static void main(String[] args) throws Exception{
	    new CONVSTR().run();
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return;}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(;}
	long nl()throws Exception{return Long.parseLong(;}
	double nd()throws Exception{return Double.parseDouble(;}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(;

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	        return st.nextToken();

	    String nextLine() throws Exception{
	        String str = "";
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        return str;

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:


nice editorial sir. I couldn’t wait till morning to see where I went wrong!


I have tried the similiar approch but Got WA.
Can’t figure out where it went wrong.

Here is the link to the code.

Can someone please figure out where I went wrong. I couldn’t figure it out.
Sample test passed and checked other cases as well.
Link to code:

Got WA, the example cases and the test cases works fine.

Here is the link to my code.

My WA code which should’ve worked only for subtask 1.
Please tell me what I’ve done wrong.

i have similar approach to do this problem but only first subtask is passing,please tell me where i am wrong ,here is my code link:

1 Like

What is wrong in my approach-
I am getting TLE, can some suggest some remedies
here is my code it may help

1 Like

Can someone please figure out where i went wrong.

will check it now, thanks!

BRO,can u please little comment yout code…

Your code fails on
abcde , aabaa
Check your output

1 Like

Video Editorial of Convert String.
(Tester Approach)
Why only partially accepted?

On this case -
smallest number of operations needed is 2
your code outputs 3


i think this case will give wrong answer.
check it out.

Can someone help me to figure out why I am getting WA in 1st subtask while getting AC in 2nd?

Thanks man, got it.