I'm having a tough time convincing myself right when coming up for some solutions to medium/hard leetcode.com problems. Take the following question for example.
Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same. If possible, output any possible result. If not possible, return the empty string. Example 1: Input: S = "aab" Output: "aba" Example 2: Input: S = "aaab" Output: "" Note: S will consist of lowercase letters and have length in range [1, 500].
On a question like this I usually work up to a solution and then try to look for counter examples. Looking for counter-examples often helps me identify where there might be holes in my approach, but it's still challenging to not fool myself.
For example I may initially have the idea to sort the string by characters, then create a new string by inserting different characters between similar characters through a process of interleaving.
e.g. `abacc` 1. Sort: `aaccb` 2. Interleave: `acacb`
Hmm.. OK seems like a decent algorithm. But then I might find a counter-example.
e.g. `ababcc` 1. Sort: `aaccbb` 2. Interleave: `acacbb`
OK, this is good as my algorithm can improve. It seems like I need to sort the strings I am interleaving by frequency possibly, but that doesn't quite work as already shown by this counter example. So maybe I can insert them by round-robin order, yes that seems to be much better.
e.g. `ababcc` 1. Sort: `aaccbb` 2. Interleave: `acabcb`
Now at this point I am fairly confident that my algorithm is correct after trying to come up with more counter-examples, unsuccessfully. However, I am still not sure that I am correct (e.g. what if sorting by some other random order produces a result that I did not cover with this approach? How can I convince myself this is not the case?)
I could perhaps say something like "ok, well since I am sorting and getting maximum variability by doing a round robin interleaving this should be correct" but there is still a part of me that is unsure that this is correct and that there isn't a counter example.
With simpler examples it's easier to convince myself correctly with a little mini-proof, or by covering the entire sample space, or by proving by contradiction or something similar, but as the questions get tougher I find myself hard-pressed to convince myself short of writing an entire proof out.
Do I just need to get better at proofing stuff like this with in a hand-wavy way like I would be able to with easier problems?
- I've already taken DS&A and all the formal algorithms courses at university.