How to write a follow up paper describing a different solution to a similar problem
There are two basic approaches to the potential issues of self-plagiarism in such a case:


First write the paper, then ensure there is no significant re-use of text by going through and paraphrasing.
Embrace the reuse and explicitly declare (with citation) which elements are adapted from the previous publication.


You will clearly need to reference and compare with the prior publication in any case, as this is obviously a closely related work.  As such, your text must be different in many ways reflecting the different context created by the first publication.  Personally, however, I would prefer to use the second strategy and perform a declared reuse of text rather than attempt to arbitrarily paraphrase just for the sake of being different.