So I solved this, sort-of.
I ended up writing a C# program in Linux using mono that takes a single argument (oldString in the function above) and returns newString to the console. To get the value of newString in PHP I'm making a call to this binary and storing the result to be used later in my script.
I'd like to find a fully native PHP method to do this but I guess that I've found a work around for the time being.