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.