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

文字列の長さを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