You don't want to tie the lifetime of the Pattern to the lifetime of the String, that attempts to borrow it for too long. The lifetime of the pattern is the lifetime the string being searched in should be borrowed for, which in this case doesn't need to be longer than the expression in the while let. What you need to do to fix it is specify that the pattern can work for any lifetime with for<'a> Pattern<'a>, and elide the separate lifetime on the string.
Corrected version of example 1
Corrected version of example 2
Note that I've also removed in_band_lifetimes since it isn't necessary here and tends to confuse things.