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: ""

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?

Extra Information:

  • I've already taken DS&A and all the formal algorithms courses at university.
  • $\begingroup$ I think this question is too broad. (Any community votes on that?) It basically amounts to "how do I prove an algorithm correct?". The answer depends on the algorithm. If you've taken the right algorithms classes, they should be showing you proofs of correctness for algorithms throughout the course, so you should have seen a bunch of examples of that already. $\endgroup$
    – D.W.
    Commented May 22, 2018 at 1:07
  • 1
    $\begingroup$ @D.W. you could definitely be correct. I mean, I could solve the problems in my algorithm classes but I can't imagine people are bringing up a full proof just to figure out if they are correct before writing solutions to these problems? I mean companies expect you to solve a lot of these on whiteboards on the spot. I'm going to revisit my algorithm textbook, hopefully I will regain some insight I have forgotten. $\endgroup$ Commented May 22, 2018 at 2:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.