Overview

This problem can be rephrased by converting the condition “vegetable total equals fruit total” for each interval into a condition on the prefix sums of their difference.
By counting pairs of positions that share the same cumulative difference, we can efficiently count all valid intervals.

Analysis

For each day: - V corresponds to \((v_i,f_i)=(1,0)\), so the difference \(v_i-f_i\) is \(+1\) - F has a difference of \(-1\) - B, N have a difference of \(0\)

The condition for an interval \([l,r]\) to be a balanced period: [ \sum_{i=l}^r vi = \sum{i=l}^r fi ] is equivalent to: [ \sum{i=l}^r (v_i-f_i)=0 ]

Now, define the prefix (cumulative sum from the beginning) as: [ Dk=\sum{i=1}^k (v_i-f_i),\quad D_0=0 ]

Then the difference sum over the interval \([l,r]\) is: [ Dr-D{l-1} ]

So the balance condition becomes: [ Dr=D{l-1} ]

In other words, we just need to count pairs of positions that share the same cumulative difference value.

---

Naively checking all intervals \((l,r)\) would require \(O(N^2)\) intervals, which is too slow for \(N\le 10^6\).
Instead, we scan from left to right once, maintaining an associative array that tracks “how many times each difference value has appeared so far.”

• Let diff be the current cumulative difference
• If at the current point cnt[diff] occurrences of the same difference have appeared in the past,
  all of them form “balanced periods ending at the current position”
• So we add ans += cnt[diff]
• Then update cnt[diff] += 1

This counts all valid intervals without duplication.

Algorithm

1. Initialize diff = 0 (cumulative difference) and ans = 0.
2. Maintain cnt (difference value → occurrence count) as a dictionary, with the initial value cnt[0]=1.
   (This represents the length-0 prefix \(D_0\). Without this, intervals starting from the beginning would be missed.)
3. Process the string S from left to right:
   • If V, then diff += 1
   • If F, then diff -= 1
   • If B or N, no change
   • ans += cnt[diff]
   • cnt[diff] += 1
4. Output ans.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)
  (The number of distinct difference values is at most \(2N+1\))

Implementation Notes

• The initialization cnt[0] = 1 is crucial.

• Since B and N do not change the difference, it suffices to update only for V and F using if/elif.

• The answer can be as large as \(N(N+1)/2\) (the total number of intervals), so Python’s int handles it safely.

  Source Code

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    S = input().strip()

    diff = 0
    cnt = defaultdict(int)
    cnt[0] = 1
    ans = 0

    for ch in S:
        if ch == 'V':
            diff += 1
        elif ch == 'F':
            diff -= 1
        # 'B' and 'N' do not change diff

        ans += cnt[diff]
        cnt[diff] += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.