You are not logged in. Please login at www.codechef.com to post your questions!

×

# M71CNTAB - Editorial

Author: nmalviya1929
Tester: manjunath1996
Editorialist: nmalviya1929

SIMPLE

None

# PROBLEM:

Given a string s consisting of a and b. Find number of subsequence "ab" in s.

# QUICK EXPLANATION:

This problem can be simplified as for each b, find the total number of a that precedes it. Answer is the summation of all the values.

# EXPLANATION:

Question can be simplified as for a particular bi ,we have to find all the subsequence "ajbi" where 0<=j< i .This value is equal to number of a's preceding b.Answer is summation of all this values.

To calculate number of a's that precede each b, we will keep a variable count that will keep track of number of a's encountered so far while traversing string from left to right. While traversing string from left to right , whenever an 'a' is encountered, we will increment count variable and wheneber 'b' is encountered we will increment answer by count.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

asked 26 Aug '17, 12:44 16114
accept rate: 0%

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,688
×643
×14

question asked: 26 Aug '17, 12:44

question was seen: 130 times

last updated: 26 Aug '17, 12:44