Don't mutate strings in cl-substitute

Don't mutate strings in cl-substitute

This fixes cl-substitute, cl-substitute-if, cl-substitute-if-not,
cl-nsubstitute, cl-nsubstitute-if and cl-nsubstitute-if-not,
when called with a string sequence argument.

* lisp/emacs-lisp/cl-seq.el (cl-nsubstitute):
Avoid running in O(n^2) time and make future-safe.

(cherry picked from commit de5a89254cb8645143e9f4e51a1727a7237109e8)