https://scratch.mit.edu/discuss/post/6991646/ への解答です。 O(|S|)です。
最初は答えを二分探索しようとしたが、考察するとO(|S|)で解けそうだったのでやってみた。 二分探索の解き方は多分O(|S|²)になる(保証はない)。
