愚直にやるなら左端と右端を決めて探索していけばよいが…

文字列の長さをN（最大2 * 10^5）として愚直に探索する擬似コードを書くと

for left = 0 ; left < N; left++
　　　　for right = 0; right < N; right++

となるがこれは計算量が最大でN * N(4 * 10^10)となり実行時間制限: 2 sec内で探索はできない。(大抵は10^8以下でないと間に合わない)

よって工夫する必要がある。rightのループ文を高速化できればN *(高速化したやつ)にできるぽい
やり方としてパっと浮かぶのは累積和としゃくとり法を使う方法。もう一つは Twitterで教えてもらった累積和と二分探索法。

これらの説明は難しいのでソースで。

解答例（C++、愚直に探索、計算量が多すぎてTLE(制限時間オーバーによる誤答)になってます ） https://atcoder.jp/contests/abc229/submissions/27567341

解答例（C++、累積和、しゃくとり法） https://atcoder.jp/contests/abc229/submissions/27565090

解答例（C++、累積和、二分探索） https://atcoder.jp/contests/abc229/submissions/27565460