You are given a string comprised of symbols `a`

and `b`

. You have to perform certain operations on it.

In each operation, you must select an occurrence of the substring `ab`

in the string and replace it with `bba`

. You must keep doing such operations until there is no occurrence of the string `ab`

.

The task for this problem is to: *Give an algorithm, whose input is such a string, and which computes the minimum number of operations until the string is free of occurrences of ab*.

This problem is a part of Tessellate S.T.E.M.S.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestWhat is the answer

Log in to reply

Algorithim !!!!

Log in to reply

can the algorithm be a computer code of c++ format like with for loops and while loops and array along with basic string functions

Log in to reply

– You are expected to describe the algorithm, possibly in the form of a pseudo-code, and describe why it is correct. Also, analyze the performance of the algorithm.

Agnishom Chattopadhyay

Log in to reply

1: str= stored string 2: str1="" 3: i=0 4: f=0 5: while (i< length of str) 6: c= character of str at i th position 7: if (c='a') f=f+1 8: elseif (c='b' and f>0) str1=str1+"bb" 9: elseif (c not equal to 'b' and f>0) str1=str1+'a', f=0 10: if (c not = 'a' or c not = 'b') str1=str1+c 11: i=i+1 12: end of while loop 13: return str1

Log in to reply

What should be the time complexity of the solution?

Log in to reply

Try coming up with the best solution that you can :)

Log in to reply

How do we need to answer above question? Write theory explaining the stuff or the pseudocode?

Log in to reply

Log in to reply

Log in to reply

Yes. I will check with the organizers and clarify this point.

I agree. However, if an algorithm designer does not prove his algorithm, how does one know that what he has proposed really does what we want it to? That said, a next best thing to a proof would be some kind of heuristic justification of why you'd think that the algorithm is correct.

Log in to reply

We stand by Balaji's words and believe that it is only through hard problems that one can assess understanding. Please give your best to the response. There will be points for the approach and the solution, and not just the answer.

Thank you On behalf of S.T.E.M.S Aalok

Log in to reply

Log in to reply

if any flaw please reply

Log in to reply

The logic is that check the number of b's after a and then replace 2x number of b's before a removing those b's

Log in to reply