LARGESUB - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

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

\max(r_a-l_a+1, r_b-l_b+1)

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)
1 Like
2

How come mine didn’t pass all the tc?

    int n; cin>>n;
    string s; cin>>s;
    int ab = 0, ba =0;
    int count = 1;
    int ans = 0;
    for(int i=1; i<n; i++){
        if(s[i-1]=='a' && s[i]=='b') ab++;
        else if(s[i-1]=='b' && s[i]=='a') ba++;
        
        if(ab==ba){
            count = i+1;
            ans = max(ans, count);
        }
        else if(ab==ba && ab==0) count++;
        else if(ab!=ba){
            ans = max(ans, count);
            count = 1;
        }
    }
    ans = max(ans, count);
    
   cout<<ans<<endl;
3

1
6
ababbb

answer should be 5 should be answer that id babbb

1 Like
4

okey

1 Like