Insert a Character to Maximize JOI Subsequences

Given a string S of length \(N\) consisting only of the characters J, O, and I, you are allowed to insert exactly one character at any position (including before the first character or after the last character). Your task is to determine the maximum possible number of subsequences (not necessarily contiguous) equal to JOI that can be obtained after the insertion.

A subsequence JOI is defined as three indices \(i < j < k\) such that the characters at these positions are J, O, and I respectively. Note that the inserted character can be chosen arbitrarily from {J, O, I} to maximize this count.

Approach: One way to solve the problem is as follows:

1. Compute the original count of subsequences \(JOI\) in S using a simple dynamic programming approach.
2. For each possible insertion position \(pos\) (from 0 to \(N\)), consider the effect of inserting each of the three characters:
   • If you insert a J at position \(pos\), all new subsequences will use the inserted J as the first letter. The additional subsequences contributed will equal the number of \(OI\) pairs in the substring \(S[pos:]\).
   • If you insert an O, the extra subsequences will be \( (\text{# of } J \text{ in } S[0:pos]) \times (\text{# of } I \text{ in } S[pos:]) \).
   • If you insert an I, the extra subsequences will equal the number of JO pairs in \(S[0:pos]\).
3. Take the maximum extra contribution over all positions and all choices, and add it to the original count.

The formulas can be summarized as:

[ \text{answer} = \text{original}_\text{count} + \max_{0 \le pos \le N} { A_J(pos), A_O(pos), A_I(pos) } ]

where:

[ A_J(pos) = \sum_{j=pos}^{N-1} \begin{cases} \text{# of }I\text{ in }S[j+1:], & \text{if } S[j]=O \ 0, & \text{otherwise} \end{cases} ]

[ A_O(pos) = (\text{# of } J \text{ in } S[0:pos]) \times (\text{# of } I \text{ in } S[pos:]) ]

[ A_I(pos) = \text{# of } JO \text{ pairs in } S[0:pos] ]

You are required to output the final maximum count.

inputFormat

The input consists of a single line containing the string S which only consists of the characters J, O and I.

outputFormat

Output a single integer: the maximum number of subsequences \(JOI\) achievable after inserting exactly one character into S.

sample

JOI

2