# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* raysh07

*sushil2006*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

Simple

# PREREQUISITES:

None

# PROBLEM:

Given a string containing only the characters `a`

and `b`

, find the length of its longest subsequence whose count of `"ab"`

substrings equals its count of `"ba" `

substrings.

# EXPLANATION:

First, let’s characterize *good* strings, i.e, those with an equal number of `"ab"`

and `"ba" `

substrings.

Let’s look at a string S, and see what happens when we move left-to-right.

Without loss of generality, S_1 = \text{a}.

As we move left to right:

- We’ll see several occurrences of
`a`

, and then the first time we come across an occurrence of`b`

, we find one occurrence of`"ab"`

as a substring. - After that, we see several occurrences of
`b`

, till we reach the next occurrence of`a`

- at which point we obtain one occurrence of`"ba"`

as a substring. - Then, the process repeats: we’ll see several
`a`

’s, then the substring`"ab"`

, then several`b`

’s followed by a`"ba"`

, and so on.

Notice that we alternately obtain occurrences of `"ab"`

and `"ba"`

.

So, for their number of occurrences to be equal, the last one we find should be `"ba"`

(since we started with `"ab"`

).

From the process above, we see that we encounter `"ba"`

last if and only if S ends with `a`

.

So, if S starts with `a`

, the number of `"ab"`

and `"ba"`

substrings will be equal only if S also ends with `a`

.

The same applies if S starts with `b`

: the number of substrings will be equal if and only if S also ends with `b`

.

In simpler words, S is *good* if and only if its first and last characters are equal.

This means we’re really just looking for the longest subsequence of S whose first and last characters are equal.

A simple way to find this is:

- Let l_a be the index of the leftmost occurrence of
`a`

in S, and r_a be the rightmost occurrence.

For the first and last characters to be`a`

, the best we can do is take every character from l_a to r_a, for a total length of (r_a - l_a + 1). - Similarly, for starting/ending with
`b`

, the best we can do is (r_b - l_b + 1).

The final answer is thus

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (PyPy3)

```
for _ in range(int(input())):
n = int(input())
s = input()
ans = 0
for c in 'ab':
l, r = s.find(c), s[::-1].find(c)
if l != -1: ans = max(ans, n-r-l)
print(ans)
```