Need help with figuring out best possible solution for this problem: There are two strings of same length representing numbers, we can swap the elements at corresponding index in both strings. There exist some integer k such that k swaps results in strings with minimum absolute difference. Task is to find k. Example of one of possible swap: s = "123" and t = "456" -> swap at index 0 makes s = "423" and t = "156" -> abs diff is 267 a possible solution is using back tracking but there should be better solution for this.

A follow-up question, given some k we want to find minimum possible absolute difference after k swaps.

Wouldn't it just be: For index 0: Put the bigger number s[0],t[0] in s, smaller one in t For every other index: Put the smaller number s[i],t[i] in s, bigger one in t

Please correct me if I'm wrong!

For the first question:

So we can get this method:

When $$$s_0 > t_0$$$, swap $$$s_0, t_0$$$, add $$$1$$$ to $$$k$$$.

for each positive integer $$$i$$$(assume $$$s_i$$$ and $$$t_i$$$ exists), when $$$s_i < t_i$$$ swap $$$s_i, t_i$$$, add $$$1$$$ to $$$k$$$.

UPD: The solution of the second question:

This is pretty similar to the solution of the first question, but when $$$a_0 > t_0$$$, we swap $$$s$$$, $$$t$$$, and except this we can do at most $$$k$$$ swaps, so we swap the digits from front to back.

And when there is some extra swaps, use these swaps on the last digit.

the k which will come would be minnimum or not

When just use this method, we cannot guarantee that $$$k$$$ is th minimum.

But replace the 1. with "When $$$s_0 > t_0$$$, swap $$$s, t$$$.", the $$$k$$$ will be minimum.